DP 15. Partition Equal Subset Sum | DP on Subsequences

[@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 ❤✌🏼

[@pervejmia8240]

@Striver , can you please a Linked List playlist? This is the most confusing topics for interview preparation i think..

[@vishalshandilya3984]

yes i did

[@thisismr900]

khub bhalo striver bhaiya, keep striving harddddd

[@AshwinHarish-u4t]

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?

[@chanchalroy3417]

Understood

[@sahilgagan2242]

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 ....

[@abdulnafe6442]

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.

[@M10-r8q7h]

@@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

[@23cash86]

@@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.

[@ok-jg9jb]

@@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

[@KunalSingh-kn2ij]

Solved this question without watching the video! DP was nightmare for me before watching your playlist. Thanks Striver.

[@Gokul-gkl]

is it?

[@vikasgupta6701]

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!!

[@guptashashwat]

It is important to check always if(arr[0]

[@ramanahlawat398]

true

[@utkarshverma3314]

@@samualhalder can you explain this condition to me, the prev question worked without with this condition whereas this one won''t

[@rishabhraj8233]

@@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'

[@shibainu7500]

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.

[@ganeshkamath89]

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.

[@spytonic4171]

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 :)

[@rishabhgupta9846]

understood,mapping of new problem with the problems we have already solved is very much important

[@preetisahani5054]

Understood. Awesome explanation! thought hard but still didn't come up with your logic. You made it so simple.

[@stith_pragya]

UNDERSTOOD..............Thank You So Much for this wonderful video...........🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻

[@shivangmishra1978]

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

[@Ashutosh_75]

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 .

[@girishbhargava6367]

Best playlist of DP, that can ever exist anywhere

[@abhijeetbasfore6816]

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

[@Sumit-wy4zp]

Understood ++; Great Explanation .. This is the greatest playlist on Earth. Day 152 ..

[@k-AnishChatti]

Understood !!!! Finally understanding Subset with DP and now I am able to solve Knapsack at 5AM 😁

[@ankurbaijal5663]

Understood !! Solved this question without watching the video!

[@aseem-b23]

Understood and thank you so much Striver ❤

[@study-yd6es]

Amazing Explaination Striverr Sirr

[@BharatiSubramanian99217]

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]

[@sauravdutta]

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.

[@well....7751]

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.

[@codingachinilgtifirbhikrrh9009]

i also did the same thing but i am not able to memoize it can u tell me what did u do?

[@vaishnavi9755]

Yes same.. but how to create tabulation for the same any idea on that??

[@sayakghosh5104]

@@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.

[@vaishnavi9755]

@@sayakghosh5104 Okay.. Got it.. Thanks for the answer!

[@rishabhinc2936]

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); }

[@udaytewary3809]

Understood bhaiya ❤❤❤ I solved this question on my own bhaiya 🎉🎉 really happy 😊😊 And this is only possible is because of u❤❤

[@yashshukla1637]

Very well explained brotha! love your content!!!!!

[@dharmeshpoladiya9047]

Understood 💯💯 Great Explanation. Thank you very much for all you efforts🔥🔥

[@GurshaanpreetSingh-b5p]

we have to set cur[arr[0]] instead of prev[arr[0]] , then it will work correctly otherwise it may give wrong answer ex -> for 1 ,2,5 where target =4 , it will give true but answer should be false Nice video Btw 👍👍

[@MukeshKumar-cc3uh]

Loving the playlist. "Understood" Sir Striver.❤

[@prabhakaran5542]

Understood ❤

[@theclashbegin4002]

Whatever you teach it's just osam .Understood .Thanks for this playlist.

[@channelname4394]

Best explanation. understood , hope this channel reaches more people

[@lakeshkumar1252]

solved by just getting hint in the first half thanks bhaiya

[@ntgrn-pr5yx]

understood , thank you striver

[@chetanchaudhary1017]

Thanks Striver !!! For such wonderful DP series

[@raghavmanish24]

understood.....waiting for finish this series as soon as possible

[@nithish_raina]

The question might have been more clear by specifying (S1 U S2 ) = A where Si is a subset and A is the original array.

[@ishantrivedi5588]

Correct! In the question they've not said that both subset should make up the entire array

[@vikasbagri1225]

understood it very well thanks for this amazing DP series

[@vanshikasoni6950]

Understood Bhaiya... Thank you!

[@shreyashtech8556]

bro doing gods work

[@AdityaPandey-ek5vq]

Ban rhe ques 🙏🏻🙏🏻 . Thank you!!!

[@hashcodez757]

"UNDERSTOOD BHAIYA!!"

[@paveshkanungo6338]

understood! Thank you Striver!

[@junaidkhalidi-mw1zs]

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]

[@probro2540]

understood Also, thank you for the song at the end. It's a nice song and has been added to my playlist 😂

[@dhruvkaran9724]

bro able to solve it myself ... with exactly same way u explained .... looks like I started thinking like legend :D hhehehe

[@sujalgupta6100]

At 8:33 why using condition if( arr[0] == k ) instead of if(arr[0]

[@nithish_raina]

It has to be

[@Divyendu-by7te]

@@nithish_raina can you please explain this to me?

[@earningonlinevip8147]

understood sir thank you sir i love you sir mzaaaaaaa gya padhke ....ab to lg rha h jaisse dp mere bacche jaisa h

[@Amitkumar-yh2uw]

cool content, very crisp and clear (Y)!

[@ananthalakshmi]

@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?

[@ranasauravsingh]

UNDERSTOOD... ! Thanks striver for the video... :)

[@shauryakumar6372]

why we are checking arr[0]

[@HammyHues]

@shauryakumar6372 exactly!! same doubt.

[@kon_humein]

​@@HammyHuesbecause bottom up approach use kiya hai with space optimisation bro memorization nhi

[@kathanvakharia]

Understood...Completed 15/56

[@shubhamraj25]

8:00 that condition is necessary to pass all test cases for the same question in LeetCode

[@arreactor2146]

Not necessary, I have submitted same question on leetcode without this condition. Just comment this line // if(nums[0]

[@ritikshandilya7075]

Thankyou so much Striver

[@shreyashtech8556]

understood at its peak

[@adarshanku7988]

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 🙏.

[@katamsreeja6744]

Understood it clearly. Thank you so much.

[@arihantjammar8888]

Understood 😃😊

[@Hrushi_2000]

Understood. Thankyou Sir.

[@gunduboinadileep9523]

understood, Sir!

[@momilijaz271]

man! you are good at DP!

[@adityajoshi3922]

that's why he made the course

[@OpenMinded2509]

can we do it if no target was given just equal sum subset

[@jyothiyadav2595]

Understoooood ❤❤❤❤❤❤❤❤

[@lambar0]

Striver, can you gather the indices for one valid solution from the tabulated dp table ? As one question is to return a solution subarray?

[@piyushsaxena6243]

understood, amazing explanation.

[@varindersingh_]

Understood. Thanks for creating the playlist.

[@Yoshitha-fq9en]

Really Nice

[@meetsaini3069]

Understood sirji

[@SnehJoshi19]

What if we have given divide in to K subset ?

[@mypherleetcoder2267]

Understood , awssmm Videos (your DP series is LIT !!)

[@parthib.1555]

Understood

[@AbhishekKumar-cv1dh]

Understood🔥🔥🔥🔥

[@SD-vk3ko]

Hey Striver... THANK YOU So much for all the efforts. I just wanted to know, what accessories you use to make the video?

[@aps8874]

Thank you so much!

[@SajanKumar-ec2us]

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

[@nithishlelll9664]

Understood!!😄

[@himanshuagrawal8012]

SAMJH GYA BHAIAYA #UNDERSTOOOOOOOOOOOOOOOOOOOOOOOOOOOODDDDDDDDDDDDDDD

[@BishtiGanika]

You are a SUPERHERO 🧡

[@Nitishsharma-y7c]

Understood👍👍

[@thisismr900]

kHUB BHALO STRIVER BHAIYA STRIVE HARDDDDD

[@anirvangoswami]

Maan Gaye guru.sticker

[@gunjjoshi5687]

good observation

[@ratinderpalsingh5909]

Understood, sir. Thank you very much.

[@lakshyasharma7448]

correct me if i am wrong but isn't the operation : prev = cur a Theta(n) operatoin...would not it be better if we could just move between two arrays ....instead of keeping the previous row in prev and current row in cur here is my implementation ...do correct me if you think what i am saying is wrong bool check(vector &arr,int n,int sum,vector &dp){ dp[0][0] = 1; dp[1][0] = 1; int init =0; for(int i=0;i

[@takeUforward]

Yes works.

[@prakhardixit1597]

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]?

[@VIKASRAJPUT-nr4nw]

sir poori dp series mein yahi lal kurta hai isko badal lo yrrrr pehle....thanks for this dp series.....suppport from IIITA

[@himanshubanerji8800]

Understood!

[@sanjanashrees30]

Does this work for array with negative values?

[@rishabhagarwal8049]

understood Sir Thank you very much

[@kevinkumar7788]

UNDERSTOOD

[@falgunitagadkar4097]

Understood Striver!✌

[@VIJAYSHARMA-dh6vo]

Understood sirrrr

[@mdrejaulhasan5108]

What about arr size is 1. Isn't it an edge case.

[@nimmalavishnu3044]

You r genius man...U r gem

[@Hard2Smart_Coder]

Understood😀

[@tech_wizard9315]

By when entire dp series will be uploaded

[@King-ul4nb]

March Tak shayad ho jayega

[@TusharKukreti-y1x]

understood....

[@saswatmishra4055]

The lectures are very good, but i am finding it difficult to understand the tabulation part of any video(will rewatch these problems in a few months and may be i will understand).

[@Codekage1]

same bro

[@kshitijgupta592]

Hey, can you make a video about what should be the size of our DP? I'm always confused between n or n+1

[@kanishkdadhich1720]

Depends, whether you require n states or n+1 states. To be on a safer side, generally ppl declare n+1 size array

[@gp7060]

Is way of finding subsequence and subset are same pick and not pickup?

[@utkarshverma3314]

how exactly is the condition if(arr[0]

[@AshishYadav-ql3up]

loved it