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 ❤✌🏼
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?
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!!
@@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'
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
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
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.
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.
@@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.
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); }
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 👍👍
@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?
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]?
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 🙏.
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.
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.
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.
is it?
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!!
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.
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 .
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.
understood,mapping of new problem with the problems we have already solved is very much important
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 :)
Best playlist of DP, that can ever exist anywhere
Understood. Awesome explanation! thought hard but still didn't come up with your logic. You made it so simple.
UNDERSTOOD..............Thank You So Much for this wonderful video...........🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
Understood ++;
Great Explanation .. This is the greatest playlist on Earth.
Day 152 ..
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 and thank you so much Striver ❤
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 !!!! Finally understanding Subset with DP and now I am able to solve Knapsack at 5AM 😁
Understood !!
Solved this question without watching the video!
Very well explained brotha! love your content!!!!!
Thanks Striver !!!
For such wonderful DP series
Whatever you teach it's just osam .Understood .Thanks for this playlist.
Loving the playlist. "Understood" Sir Striver.❤
Understood bhaiya ❤❤❤
I solved this question on my own bhaiya 🎉🎉 really happy 😊😊
And this is only possible is because of u❤❤
Understood 💯💯 Great Explanation. Thank you very much for all you efforts🔥🔥
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?
bro doing gods work
Understood ❤
understood.....waiting for finish this series as soon as possible
Best explanation. understood , hope this channel reaches more people
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.
understood! Thank you Striver!
understood
Also, thank you for the song at the end. It's a nice song and has been added to my playlist 😂
understood it very well
thanks for this amazing DP series
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);
}
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 👍👍
understood , thank you striver
Understood Bhaiya... Thank you!
"UNDERSTOOD BHAIYA!!"
cool content, very crisp and clear (Y)!
solved by just getting hint in the first half thanks bhaiya
understood sir thank you sir i love you sir mzaaaaaaa gya padhke ....ab to lg rha h jaisse dp mere bacche jaisa h
bro able to solve it myself ... with exactly same way u explained .... looks like I started thinking like legend :D hhehehe
Ban rhe ques 🙏🏻🙏🏻 . Thank you!!!
why we are checking arr[0]
@shauryakumar6372 exactly!! same doubt.
@@HammyHuesbecause bottom up approach use kiya hai with space optimisation bro memorization nhi
can we do it if no target was given just equal sum subset
Understood. Thankyou Sir.
understood, Sir!
Thankyou so much Striver
UNDERSTOOD... !
Thanks striver for the video... :)
understood, amazing explanation.
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]
Understood it clearly. Thank you so much.
understood at its peak
man! you are good at DP!
that's why he made the course
Understood 😃😊
Really Nice
Understoooood ❤❤❤❤❤❤❤❤
@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?
Striver, can you gather the indices for one valid solution from the tabulated dp table ? As one question is to return a solution subarray?
You are a SUPERHERO 🧡
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. Thanks for creating the playlist.
What if we have given divide in to K subset ?
how exactly is the condition if(arr[0]
Understood
Understood sirji
Understood!!😄
Understood , awssmm Videos (your DP series is LIT !!)
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]?
Understood...Completed 15/56
Understood🔥🔥🔥🔥
How to print this sequence ?
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]
Thank you so much!
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 🙏.
SAMJH GYA BHAIAYA #UNDERSTOOOOOOOOOOOOOOOOOOOOOOOOOOOODDDDDDDDDDDDDDD
good observation
Understood!
Maan Gaye guru.sticker
1st comment. Luv u bhaiya❤️❤️
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 Striver!✌
Understood, sir. Thank you very much.
Does this work for array with negative values?
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
kHUB BHALO STRIVER BHAIYA
STRIVE HARDDDDD
Understood sirrrr
loved it
You r genius man...U r gem
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
Master piece 💥❤️
Understood😀
understood Sir Thank you very much
Is way of finding subsequence and subset are same pick and not pickup?
understood ❤
understood!
What about arr size is 1. Isn't it an edge case.
Understood sir
Thank you