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 ❤✌🏼
I'll be honest, I was bamboozled with the 0's in array edge case since DP17 and I was simply unable to find a clear answer from the comments. Had I simply closed my eyes and went ahead with DP 18, I would have legit saved ~ 2 hours of confusion!! Thankyou so much Striver, this lecture cleared all my doubts 🔥🔥🔥🔥🔥
Those confusion and doubts and 2 hours will only help in longer run. Good work on not directly jumping to another video without clearing your doubts on your own.
but aditya verma always tell you the in=dentification and where u can use this apparoach nd similar questions he is the god of cp ik he skip the case of 0 in array but aditya verma is for cp where u can use which approach and how to identify which approach by seeing solution
Another modified target could be (difference + totalSum)/2; To explain this how this came is : s1= sum of elements in subset 1 s2 = sum of elements in subset 2 s1 - s2 = d (We need to find 2 subsets with difference d ) s1 + s2 = totalSum (We know the sum of 2 subsets would be equal to the total sum of array) Adding these 2 equations , we get s1 = (d + totalSum)/2, thus we only need to find a subset with sum s1.
Thank you striver ! Just a note : writing recursion from 0 to n-1 looks far easier to handle bases cases than writing recursion from n-1 to 0 on subsequence problems
For Those who did not understand why total sum-d has to be even so imagine totalsum=15 and d=2 now count s2=(15-2)/2 it will give s2=6; ans s1-s2=d so s1=2+6=8 now here it is said that s1+s2=totalsum but s1+s2=14 which is not equal to total sum to total sum-d has to be even
For Problem 17 , I struggled a bit in Tabulation while writing the base cases for the new changes. All 3 cases covered, also notice the bases cases are written in reverse order, so that the priority is given to the last one if its true. One more thing since we are considering the case for i = 0, please start the 2nd loop of target from 0 till k(inclusive). Happy learning! dp[0][0] = 1 if arr[0]
To deal with the 0 case, we can also take the dp array to be of size [n+1][sum+1] and initialize the dp[n][0]=1 int[][] dp = new int[n+1][sum+1]; dp[n][0]=1; for(int index=n-1;index>=0;index--)
us But i got confused as in DP 18 ques , it is written that two partitions have their union as Whole array . It should have been given that both are exclusive of each other , for being self-explanatory well.
bhaiya in count subset problem which u had taken earlier , in tabulation the loop started from 0 to sum but when sum==0 it has been handled previously right? then it should start from 1 right? as in problem subset sum==k u started the sum loop from 1 to sum as for sum==0 we have handled it previously before the loop.
@@takeUforward yes i did that in the count subsets problem, but when I did that in the current problem of partition i.e. looping from 1 to sum it's giving WA, but when i changed to 0 to sum it's giving correct and. Why so?
Other was is just check when you reach end of nums int rec (int pos, int [] nums , int target,int sum, int mem [] []){ if(pos == nums.length){ if(target==0 ) return 1; return 0; } if( mem[pos][target]!=-1) return mem[pos][target]; int take =0; if(target>=nums[pos]){ take = rec(pos+1,nums,target- nums[pos],sum,mem); } int nonTake = rec(pos+1,nums,target,sum,mem); mem[pos][target] = nonTake+take; return mem[pos][target]; }
What if we find with target = totalsum Then at n-1 iteration of tabulation find S1 and S2 by totalsum - S1. Then If S1>=S2 and S1-S2=D we can return True else False
for DP 17 for [ 7,1,0,2,5] with tar=7 Method 1: originalAns*(pow(2,n)) Method2: Changes in base case will that work? I can see from recursion tree there would be redundant calls at level where 0 is considered
Method 1 is time intensive if let's say the no of zeroes were 15-20 in an array...Hence method 2 with handling zero in the base cases is required at such cases.
@@abhishekgururani6993 Simple base case, if sum == 0, return 1; means fill all the 0 indices row with 1. The change is that you have to traverse j=0 to j
if(k==0) dp[ind][k]= 1; if(ind==0) return (arr[ind]== k)?1:0; I feel like not returning and instead adding 1 to the dp should do the trick And in case of tabulation: dp[0][0] = 1; this should do instead of the for loop of ind= 0 to n-1{dp[i][0] =1}
you don' t even need this , just go from 0 -> n , and if at n , target == 0, return 1 else 0 , all other cases are already been taken care off , if you do in this way . How ? our code will do this will we are making the recursive calls at n-1
In the space optimized solution why the loop sum=1 to target doesn't work as we have been doing previously and setting curr[0] =1 since for any index with target as 0 there is only single subset. Can someone explain please?
if we keep base condition like this then we dont have to check for individual case ....this is giving right answer..... if(i==n){ if(s1==0)return 1; return 0; } if(s1
if someone is going from 0 to n if(i==arr.length) { if(tar==0) return 1; else return 0; } this will handle the case for zero (1, 0,0 ) will give -> 4 (if tar = 1)
int gfg the case where 0 can be in the begining can be solved by sorting given array in decreasing order but this will increase time compl,but will still pass test cases;
at 15:53 , the target should run from 1 to sum right? we have run from 1 to sum in the count subsequences with sum k also, why did you take from 0 to sum?
