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 ❤✌🏼
what if test case in dp17 is like {2, 0 , 0 , 4 , 2 ,2} and sum = 4 , then will this solution work ? i guess at the time whenever we found sum == 0 at index > 0 , then we have to calculate number of zero till index == 0 let's suppose it is z , and then retum 2^z . What everyone think about it ?
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
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--)
@@aryarajendra1088 try doing mod with 10^9+1 dp[row][col] =(dp[row][col]%mod+ dp[row-1][col]%mod)%mod; int val = num[row-1]; if(col>=val){ dp[row][col] =(dp[row][col]%mod+ dp[row-1][col-val]%mod)%mod; }
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
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.
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?
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
hey can't we do it like this remove the base case to this idx < 0 then if sum == 0 return 1 or else 0; now what will happen is if idx == 0 and sum == 0 then we will use take and notTake both, but if only sum is 0 but not arr[0] then only notTake and when sum == arr[0] and both are not zero then only Take will execute so eventually u don't have to write 3 lines of extra code right?
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]
i thnk a sligh change in base case can handle all the case well,instead of returning when we encounter the target to 0; if we keep exploring until the end of the tree then we can get our desired result class Solution { public: int helper(int arr[], int n, int sum, vector& dp) { // Base case: If there are no elements left if (n == 0) { return (sum == 0) ? 1 : 0; } // If the subproblem has already been solved, return the stored result if (dp[n][sum] != -1) return dp[n][sum]; // Compute the result for this subproblem int notPick = helper(arr, n - 1, sum, dp); int pick = 0; if (arr[n - 1]
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.
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?
I have a doubt. The question says the the union of two subsets will give the original array , that means there can be repeating elements and its not necessary that S1 + S2 = totalSum E.g -> arr = {1, 2, 3, 4, 5} totalSum = 15 S1 = {1, 2 ,3, 4} S2 = {1, 5} sum1 = 1 + 2 + 3 + 4 = 10 sum2 = 1 + 5 = 6 The union of the above two will give original array but sum1 + sum2 != totalSum. So how is the code working ? Is the problem statement wrong?
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?
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.
''' Carefully analyze the problem. Let S1, S2 be the sum of two different subsets S1 + S2 = total_sum of array elements Goal: Count the subsets, such that (S1 >= S2) and (S1 - S2 = D) total_sum = S1 + S2
=> S1 = total_sum - S2 From S1 - S2 = D total_sum - S2 - S2 = D S2 = (total_sum - D) // 2 (or) S1 = (total_sum + D) // 2 Problem boils down to finding number of subsets whose sum is (total_sum - D) // 2 (or) sum is (total_sum + D) // 2 '''
''' Space Optimization ''' if not arr: return 0 total_sum = sum(arr) target = (total_sum - d) // 2 # print('Target: ', target) if (total_sum < d) or (total_sum - d) % 2 != 0: return 0 mod = 10 ** 9 + 7 prev = [0 for t in range(target + 1)] # Base Cases # 1. At index 0, if val == 0 => 2 (pick/ unpick doesn't matter) # 2. Else, At index 0, val 1 way (pick it) prev[0] = 2 if arr[0] == 0 else 1
@@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
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
we can also do like this, private static int count(int i, int[] num, int k){ if(i == num.length){ if(k == 0){ return 1; }else{ return 0; } } int take = 0; if(k >= num[i]) take = count(i + 1, num, k - num[i]); int notTake = count(i + 1, num, k); return (take + notTake) % MOD; }
The condition is necessary because we are declaring dp vector of size n×(tar+1) so lets if our arr[0]th element is greater then tar (arr[0]>tar) then if we do dp[0][num[0]] it will give us TLE as we fixed its size to (tar+1) but we are storing value at a index which does not exist so thats why that condition is important. Hope u understand ;)
Below code is failing on 7th test case, giving wrong answer. Can someone help in finding what is the mistake I am making. int countParts(vector &arr, int sz, int d, int index, int s1, int s2, vector &dp){
if(index == -1){ if(s1>=s2 and s1-s2 == d) return 1; return 0; } int mod = 10e9 + 7;
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
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 ❤✌🏼
understood
Understood
what if test case in dp17 is like {2, 0 , 0 , 4 , 2 ,2} and sum = 4 , then will this solution work ? i guess at the time whenever we found sum == 0 at index > 0 , then we have to calculate number of zero till index == 0 let's suppose it is z , and then retum 2^z . What everyone think about it ?
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.
for real should have moved on to this video those comments were so confusing
Samee
sameeeeeeeeeeee
hats off man,, spent 2 hours on DP17 to fix that but after watching this DP 18 everything went super smooth
lol same it was worth it though
Striver's concept explanation is so cool, easy and easily get stuck into the head. I wish to meet him one day and say a lot of thanks to him.
understood until 14:00 ❤ .
Will learn the optimization later
The deduction of (totalSum - D) / 2 was amazing. Understood!
Understood! Hats off to ur dedication, u are still teaching while suffering from fever.
Already understood before starting of video that's what Striver teaches us
I studied DP from aditya verma, but was never able to figure out how to handle the zeros in the array, you made it super easy, Thanks!
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
@@entertainmenthub373 God of cp is tourist.
its not like he was not able to figure out , he always gives an intution to solve the problem , not like come and tells you the whole solution.
aditya vermas approach works with zeroes as well, as in that we subtract dp[i-1][j-arr[i-1]]
Us, but the way you transformed the problem into previously solved problem is amazing , that's the way we have to think ... Thanks ❤
we can also use :
if(ind < 0){
if(sum==0) return 1;
return 0;
}
apart from these conditions:
if(ind == 0) {
if(sum==0 || num==arr[0]) return 1;
if(sum==0 && arr[0]==0) return 2;
return 0;
}
this makes the code really simple to understand. perfect base case.
Best Bhai
@@anuragprasad6116
but how will you handel -1 index in tabulation?
UNDERSTOOD.........Thank You So Much for this wonderful video...............🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
The lecture is awesome as always. Thank you so so much for making these videos even when you are sick. You inspire me to work hard. Thank you again :)
Superb Bhaiya
guys watch at 10:10
Amazing Concept
Again and again Thankyou bhaiya Aka Striver
4:48 or I think, we can go 1 step deeer into indx = -1
then base case would be simpler
if (indx == -1) {
if (sum == 0) return 1;
else return 0;
}
Then how do you take care of base case in Tabulation. As dp array cannot have -ve indexes.
@@introvert9112k for that i think we would need to make 1 indexed arrays of size n+1 having an extra 0 index free
Understood! Striver. The best Software Engineer himself
After this video, they updated the problem! Real influencer
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--)
Hello,
The tabulation code is not passing all test cases in both videos dp-17 && dp-18. Is anyone facing the same problem. Pls HELP.
same bhai
@@aryarajendra1088 #include
int countPartitions(int n, int d, vector &a) {
// Write your code here.
long long sum=0;
for(int i=0 ; i
@@aryarajendra1088 try doing mod with 10^9+1
dp[row][col] =(dp[row][col]%mod+ dp[row-1][col]%mod)%mod;
int val = num[row-1];
if(col>=val){
dp[row][col] =(dp[row][col]%mod+ dp[row-1][col-val]%mod)%mod;
}
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
but for me it creates problem while writing the tabulation form. Esp. with all the subsequences questions.
yeah man, we have to start from n-2 if we do 0 to n-1 in recursion@@santoshpokhrel7693
yaa bro really it creates confusion in tabulation
@@santoshpokhrel7693
Understood
Thank you striver🙌🙌
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.
But this will increase the space req :)
@@takeUforward Oh Okay , I didn't think about that !
@@chetanthakral5322 lol, I thought the same thing, but its not pure math its cs.
@@varunaggarwal7126 how this increases the space.. can u explain
@@UCSParnashreeDas it's been 1 month,lol i have to revise this dp, but I guess you can see + sign while striver is subtraction, means less
Thanks to striver i could come up with using DP-17 by my own including the edge cases
Understood 👍. Hats off to your dedication for us. ♥
"UNDERSTOOD BHAIYA!!"
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.
Yes u can, won’t be an issue :)
@@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?
@@aryanagrawal4794 because in partition at 0 there are other cases to handle. Here at 0, its take and notTake, hence
@@takeUforward ok bhaiya got it.
@@aryanagrawal4794 Hey can you explain it to me?
Done. Understood the concepts so well.
another base case(Better and Concised):
if(ind
Understood 💯💯Great Explanation. Thank you very much for all you efforts🔥🔥
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
thankyou my guy🙌
For tabulation, we can do dp[0][0]=1 and
dp[0][nums[0]]+=1
Without checking for all cases
solved this problem on my own very proud of this
hey can't we do it like this remove the base case to this idx < 0 then if sum == 0 return 1 or else 0; now what will happen is if idx == 0 and sum == 0 then we will use take and notTake both, but if only sum is 0 but not arr[0] then only notTake and when sum == arr[0] and both are not zero then only Take will execute so eventually u don't have to write 3 lines of extra code right?
15:00 the most important point to be noted if you are in an intervie
Understood better than ever!
#Understood #DP18 #Hatsoff #Striver
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]
Hey, thank you. Great comment.
At 15:15, shouldn't the condition be ((nums[0] != 0)&&(nums[0] == target)) ??
understood. Also thanks for explaining Space Optimization so good. I am from tier-3 mechanical never knew all these stuff
Great Explanation Striver , Thanks
understood , thank you striver
I thing the simplest way to get rid of so many conditions of 0's we can simply start the recursion for 0 to n-1; then we will get correct ans i.e.4;
Yes, and it would also work even if the array doesn't contains any zeroes.. The base cases are also so simple to handle over here.
can u share the code here please that starts from 0 & ends at n-1
@@VinayKumar-xs6el will share soon, i also have to check where i have written the code. It's been 2 years
Thankyou very much for explaining base case of last question. I was stacked for last 6 hours. ❤️❤️
i thnk a sligh change in base case can handle all the case well,instead of returning when we encounter the target to 0; if we keep exploring until the end of the tree then we can get our desired result
class Solution {
public:
int helper(int arr[], int n, int sum, vector& dp) {
// Base case: If there are no elements left
if (n == 0) {
return (sum == 0) ? 1 : 0;
}
// If the subproblem has already been solved, return the stored result
if (dp[n][sum] != -1) return dp[n][sum];
// Compute the result for this subproblem
int notPick = helper(arr, n - 1, sum, dp);
int pick = 0;
if (arr[n - 1]
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.
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?
UNDERSTOOODD!!!
Thank you, Striver!!
understood , the space optimization is amazing sir
Understood 💯💯Great Explanation
I have a doubt.
The question says the the union of two subsets will give the original array , that means there can be repeating elements and its not necessary that S1 + S2 = totalSum
E.g -> arr = {1, 2, 3, 4, 5}
totalSum = 15
S1 = {1, 2 ,3, 4}
S2 = {1, 5}
sum1 = 1 + 2 + 3 + 4 = 10
sum2 = 1 + 5 = 6
The union of the above two will give original array but sum1 + sum2 != totalSum.
So how is the code working ? Is the problem statement wrong?
you are right code is only passing 6 test cases not all
the question's wording is wrong, look at the same question on gfg, won't see "union" written anywhere.
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?
Understood, well explained.
ok
That algebra at 10:15 is crazy I would never see that under the time constraints of a real interview. It's brilliant tho
thanks for another great video
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
How do I write the base case in tabulation, Could you please tell me?
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.
Python implementation:
def countPartitions(n: int, d: int, arr: List[int]) -> int:
'''
Carefully analyze the problem.
Let S1, S2 be the sum of two different subsets
S1 + S2 = total_sum of array elements
Goal: Count the subsets, such that (S1 >= S2) and (S1 - S2 = D)
total_sum = S1 + S2
=> S1 = total_sum - S2
From S1 - S2 = D
total_sum - S2 - S2 = D
S2 = (total_sum - D) // 2 (or)
S1 = (total_sum + D) // 2
Problem boils down to finding number of subsets
whose sum is (total_sum - D) // 2 (or)
sum is (total_sum + D) // 2
'''
'''
Space Optimization
'''
if not arr:
return 0
total_sum = sum(arr)
target = (total_sum - d) // 2
# print('Target: ', target)
if (total_sum < d) or (total_sum - d) % 2 != 0:
return 0
mod = 10 ** 9 + 7
prev = [0 for t in range(target + 1)]
# Base Cases
# 1. At index 0, if val == 0 => 2 (pick/ unpick doesn't matter)
# 2. Else, At index 0, val 1 way (pick it)
prev[0] = 2 if arr[0] == 0 else 1
if arr[0] != 0 and arr[0]
You have literally made dp look so easy !
Nicely Explained! Understood!
Understood...Completed 18/56
why doesnt the
for(int i = 0;i
bro doing gods work
Understood ❤
Guys! For DP 17, Memoization code, striver's approach is correct (6:38), but here's a cleaner alternative for the base case:
if(ind
It'll be hard to convert this base case to tabulation dp states as it's not well defined wrt the indices.
@@abhishekgururani6993 You're right. But the tabulation base cases are straightforward and simple. One can write that by applying basic logic.
Yes, I also tried this. got correct in both tabulation and memoization. Striver has complicated this solution a little bit.😅
@@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
at 14:03
why you removed
for()
dp[i][0]=1;
Understood Bhaiya!
understood. Thank you so much
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
Understood
Thanks Striver for this Dp series
Understood. Thankyou sir.
If we have handled the case num[0] == 0 previously then why we are checking it again for num[0]
Can anyone please explain why target is starting from 0 here? in all other problems it's starting from 1. If I take 1, some test cases are failing
please tell us the time when this amazing course will get end......expected time??
March
UNDERSTOOD... !
Thanks striver for the video... :)
In lecture 17, can we handle the cases having zeroes by just multiplying our previous answer with pow(2,n) where n is the no. of zeroes
I discussed that only, but that adds a log n
@@takeUforward Does 1ll
Thanks a Lot Striver 🥰
OMG bhaiya ...simple "genius"
Instead of changing the code we can just add a if statement before "take" variable that if arr[index]== 0 then skip it...
wouldn't it be better to go an ind
UNDERSTOOD
*********** Iterative Code for the count number subsequence whose sum is k ( & 0
we can also do like this,
private static int count(int i, int[] num, int k){
if(i == num.length){
if(k == 0){
return 1;
}else{
return 0;
}
}
int take = 0;
if(k >= num[i]) take = count(i + 1, num, k - num[i]);
int notTake = count(i + 1, num, k);
return (take + notTake) % MOD;
}
Thank you so much!
just mind blowing how you came up with the modified target, kyse kar lete ho bhaiya?
understood sir🙂
Is the condition num[0]
The condition is necessary because we are declaring dp vector of size n×(tar+1) so lets if our arr[0]th element is greater then tar (arr[0]>tar) then if we do dp[0][num[0]] it will give us TLE as we fixed its size to (tar+1) but we are storing value at a index which does not exist so thats why that condition is important. Hope u understand ;)
@@neerajgarg9096 THANK YOU SO MUCH! my brain was hurting thinking why but now i see
Understood 🔥🔥
test cases are not passing for recursive solution. any solution?
Hare Krishna..!! understood.
we can sort also striver to deal with 0s in dp17?? but that works only when sum is not equal to zero😅
DP 18 starts from 7:25
understood bhaiya
Understood Sir.
sir i have a doubt how should i ask like its in code
completed subsequences set problems great learning
Understood. Best on whole yt.
understood ❤❤🤞🤞🤞🤞🤞🤞🤞🤞
Striver can you explain the approach when there are negative elements also in the array
use a map
@@sarthakkrishna3492 how ?
can you explain with example
Below code is failing on 7th test case, giving wrong answer. Can someone help in finding what is the mistake I am making.
int countParts(vector &arr, int sz, int d, int index, int s1, int s2, vector &dp){
if(index == -1){
if(s1>=s2 and s1-s2 == d) return 1;
return 0;
}
int mod = 10e9 + 7;
if(dp[index][s1] != -1) return dp[index][s1];
int pick = 0, notPick = 0;
if(s1>=s2) pick = countParts(arr, sz, d, index-1, s1-arr[index], s2+arr[index], dp);
if(s1>=s2)notPick = countParts(arr, sz, d, index-1, s1, s2, dp);
return dp[index][s1] = (pick%mod + notPick%mod)%mod;
}
int countPartitions(int n, int d, vector &arr) {
int totSum = 0;
for(auto &val: arr) totSum += val;
vector dp(n+1, vector(totSum+1, -1));
return countParts(arr, n, d, n-1, totSum, 0, dp);
}
In that case my recursive code was going from 0 to n-1 and to avoid case of zero I sorted my array hence all the zero cases were sorted
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
Thank you striver, made it super easy and interesting to learn DP. "UNDERSTOOD" 💓💓