DP 15. Partition Equal Subset Sum | DP on Subsequences
ฝัง
- เผยแพร่เมื่อ 1 ก.พ. 2022
- Lecture Notes/C++/Java Codes: takeuforward.org/data-structu...
Problem Link: bit.ly/34iIIsH
Pre-req for this Series: • Re 1. Introduction to ...
a
Make sure to join our telegram group for discussions: linktr.ee/takeUforward
Full Playlist: • Striver's Dynamic Prog...
In this video, we solve the problem of Partition Equal Subset Sum. This problem is the second problem on DP on Subsequences Pattern. Please watch DP 14 before watching this.
If you have not yet checked our SDE sheet, you should definitely do it: takeuforward.org/interviews/s...
You can also get in touch with me at my social handles: linktr.ee/takeUforward
I need your support, and you can do that by giving me a like, and commenting "understood" if I was able to explain you.
Keeping a like target of 500 ❤✌🏼
@Striver , can you please a Linked List playlist? This is the most confusing topics for interview preparation i think..
yes i did
khub bhalo striver bhaiya, keep striving harddddd
Sir I have a doubt. if the first sub problem gives true and second sub problem gives false. Then result will be true since we are not passing the sub problem again to find right sub array is equal or not and also the first sub problem is true so we will give true as answer but the result is false. So it is correct?
Understood
Solved this question without watching the video!
DP was nightmare for me before watching your playlist.
Thanks Striver.
It is important to check always if(arr[0]
true
@@samualhalder can you explain this condition to me, the prev question worked without with this condition whereas this one won''t
@@utkarshverma3314 so with this condition we are checking that dp[0][arr[0]] is actually present in dp matrix because the size of row is equal to sum and if we do not check this it will go out of bounds and give error'
Yea I was also scratching my head to solve the runtime error until I saw the full video and came to know about this condition.
28% done ...... now i feel confident .. THANKS striver bhaiya for this ..... i pray u will achieve everything u want ..... god will bless u always .... u help student who cant afford courses ....
I hava doubt please help !
In memoization technique , when to declare a 2d array and when to declare 1d array to store previous answers.
Like I cannot find out which type of array should I declare .
Thanks.
@@abdulnafe6442 if there are two variable change in basic recursion like findsum(n-1,k-1) then 2d dp else if there is only one variable change in recursive function like fibonaci(n-1) then 1d dp
@@abdulnafe6442 after writing recursive code, look at all parameters, if values of only 1 parameter(eg.index) keeps changing it is 1d dp, declare 1d array ... if two parameters change (e.g. index,target) then 2d array should be declared.
@@abdulnafe6442 Don't try to write memorization first try to do recursion and see what are the parameters that are changing and make memorization. You will get it
Your video makes the tough one's look so easy. When I started with this problem, I was confused on how to proceed with this. Once, I saw the explanation, got to know that this is a new version of previous question. Thanks!!
Thanks Striver. Understood.
I think it is better to take an unordered_map instead of vector. Like this:
unordered_map prev, curr;
instead of
vector prev(k + 1, false), curr(k + 1, false);
because target value 'k' can be really large and cause lot of space wastage.
you are a gem to the community bro plz continue this trend after following your videos I'm improving logic building the way you teach and the efforts you are keeping are just amazing expecting a like from you :)
You have a very long life I picked up my phone after doing some dp question to check if Bhaiya posted video or not and daam immediately i received notification of your video 😍😌sukoon
understood,mapping of new problem with the problems we have already solved is very much important
Understood. Awesome explanation! thought hard but still didn't come up with your logic. You made it so simple.
Thanks Striver !!!
For such wonderful DP series
Understood !!!! Finally understanding Subset with DP and now I am able to solve Knapsack at 5AM 😁
Whatever you teach it's just osam .Understood .Thanks for this playlist.
Understood 💯💯 Great Explanation. Thank you very much for all you efforts🔥🔥
UNDERSTOOD..............Thank You So Much for this wonderful video...........🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
understood it very well
thanks for this amazing DP series
At end u added a if condition but I think its just :
if(arr[0]==k)prev[arr[0]]=true .
It should not be if(arr[0]
Great explanation didn't even need to see the whole video just saw the first 3 minutes and I was like it is too easy .
Best playlist of DP, that can ever exist anywhere
Understood it clearly. Thank you so much.
Best explanation. understood , hope this channel reaches more people
why we are checking arr[0]
Hey understood.
One question is: let's say our array was [1,1,2,3] and target = 4.
In the base condition dp[o][arr[0]] = true. We are checking if(arr[0]
dp[0][arr[0]] means that if you're at index 0 and the target that you have is equal to the value of arr[0] then it's true. It basically tells that when you're at index 0 and if the target is 1 in our case (which is arr[0]) then mark it as true.
without watching this video I have solved the question. easy tha bas sum/2 krna hga. if sum odd return false else subsetsum with sum/2. thank you so much Striver bhaiya
Understood and thank you so much Striver ❤
Hey Striver... THANK YOU So much for all the efforts.
I just wanted to know, what accessories you use to make the video?
Understood ++;
Great Explanation .. This is the greatest playlist on Earth.
Day 152 ..
Understood. Thanks for creating the playlist.
cool content, very crisp and clear (Y)!
Loving the playlist. "Understood" Sir Striver.❤
UNDERSTOOD... !
Thanks striver for the video... :)
Striver, can you gather the indices for one valid solution from the tabulated dp table ? As one question is to return a solution subarray?
understood! Thank you Striver!
I got a different recursion logic , although its a bit lengthy. Here each value can be included in subset 1 or in subset 2.So we write recursion for it and try to find wether for any subsets both of their sums are equal or not.
i also did the same thing but i am not able to memoize it can u tell me what did u do?
Yes same.. but how to create tabulation for the same any idea on that??
@@vaishnavi9755 You can memoize/tabulate with the help of 3D Dp, dp[index][sum1][sum2], but the constraints are too high, it'll give you memory limit exceeded.
@@sayakghosh5104 Okay.. Got it.. Thanks for the answer!
i tried using what u said but its giving me runtime and tle .can u help find error
bool f(int arr[],int n ,int sum1 ,int sum2,vectordp)
{
if(n==0)
{
return abs(sum1-sum2)==arr[0];
}
// pick
if(dp[n][sum1][sum2]!=-1)
{
return dp[n][sum1][sum2];
}
bool pick = f(arr,n-1,sum1+arr[n],sum2,dp);
// not pick
bool not_pick = f(arr,n-1,sum1,sum2+arr[n],dp);
return dp[n][sum1][sum2]=(pick || not_pick);
}
Understood, sir. Thank you very much.
understood
Also, thank you for the song at the end. It's a nice song and has been added to my playlist 😂
understood, amazing explanation.
Understood. Thankyou Sir.
Understood bhaiya ❤❤❤
I solved this question on my own bhaiya 🎉🎉 really happy 😊😊
And this is only possible is because of u❤❤
In the current problem, would the arr[i] be greater than the target only if we have negative elements? Since we are obtaining the target by summing the elements up?
If there are negative elements in the array, the range of target in the defined dp will have to change to 2 * target + 1, correct? And we will need to offset each sum value value by adding target to it to make it within the positive range of [0, 2*target]?
Thankyou so much Striver
Thank you so much!
Understood , awssmm Videos (your DP series is LIT !!)
bro doing gods work
bro able to solve it myself ... with exactly same way u explained .... looks like I started thinking like legend :D hhehehe
@takeUforward
Striver, your classes are amazing . Please keep on going......💥💥💥💥💥💥.
I have a doubt like what if array contains arr = [100] ?? ?
does the above code support above test case?
At 8:33 why using condition if( arr[0] == k ) instead of if(arr[0]
It has to be
@@nithish_raina can you please explain this to me?
What if we have given divide in to K subset ?
understood at its peak
understood, Sir!
Is way of finding subsequence and subset are same pick and not pickup?
I hava doubt please help !
In memoization technique , when to declare a 2d array and when to declare 1d array to store previous answers.
Like I cannot find out which type of array should I declare .
Thanks.
understood!!
You r genius man...U r gem
good observation
understood!
Understoooood ❤❤❤❤❤❤❤❤
Understood ❤
You are a SUPERHERO 🧡
Understood Thank you so much :)
can we do it if no target was given just equal sum subset
Understood as always. Thanks
solved by just getting hint in the first half thanks bhaiya
Understood, thanks!
Understood!!Thank you
Really Nice
Understood!
Understood👍👍
understood Sir Thank you very much
understood. And thank you.
Understood🔥🔥🔥🔥
Understood!!😄
Understood !!
Understood❤
Understood, thanks a ton
understood well bro
The question might have been more clear by specifying (S1 U S2 ) = A
where Si is a subset and A is the original array.
Correct! In the question they've not said that both subset should make up the entire array
understood
how exactly is the condition if(arr[0]
Understood...Completed 15/56
understood.
Please make a video on "Partition to K equal Sum subsets"........i can't find any dp solution understandable. Please please please make a video on its dp approach god please. Humble request bhaiya, please. Btw understood 🙏.
understood sir thank you sir i love you sir mzaaaaaaa gya padhke ....ab to lg rha h jaisse dp mere bacche jaisa h
understood. thanks
Understood 😃😊
i did not understood when if a subset is present in array then other equal sum subset will present definitely also discuss is it memoisation problem
Understood sir
TQ
Understood!!!
Understood thanks :)
Understood😀
Understood.
Understood
8:00 that condition is necessary to pass all test cases for the same question in LeetCode
Not necessary, I have submitted same question on leetcode without this condition.
Just comment this line
// if(nums[0]
Great. Understood.
Can anyone help me to write a code to print the K subsets with equal sum..
Condition is that we can only a element once in a subset..
Input- 1 2 2 3 3 4 5
K=4
Maan Gaye guru.sticker
Hey, can you make a video about what should be the size of our DP?
I'm always confused between n or n+1
Depends, whether you require n states or n+1 states. To be on a safer side, generally ppl declare n+1 size array
But there may be case that, no. of elements are even but subsets elements are not counting to same.
eg [6,6,4,4,2,2]
6+6=12(2 elements) and 4+4+2+2=12(4 elements)
Plz someone explain.
UNDERSTOOD!! 😁