Count subsets with given sum | Dynamic Programming

This video explains a very important dynamic programming interview problem which is a variation of 01 knapsack and also a variation of subset sum problem.In this problem, we are given an array and a sum value X, we need to count the number of subsets with the given sum X which can be formed from the array.I have explained the problem using examples.I have shown both the recursive as well as tabulation dynamic programming approach for this problem.I have explained the intuition and also the modifications needed to convert subset sum problem to this problem.If you find any difficulty or have any query then do COMMENT below. PLEASE help our channel by SUBSCRIBING and LIKE our video if you found it helpful...CYA :)

========================================================================
Join this channel to get access to perks:

=======================================================================

USEFUL LINKS:

#subsetsum #01knapsack #dp

[JasbirSingh-kpeu]

I already guessed the solution before you explained it because of your awesome explanation on 0 1 knapsack and subset sum problem...one of the best videos I've ever watched on this topic

[iamparitosh]

Best playlist;
Dynamic programming was so hard for me and there was no resource where it was explained in so much detail!
Thanks for the good work.

[shilpaaggarwal]

Watching this series from the beginning. Every video is fairly simple to understand and just "awesome". I liked the fact that you explain each and every problem with Recursion first and then using the DP method. This method helps me to understand the problems better and actually, the base for the DP problems (in general) is getting stronger with each video of this series.

Thank you!

[dayanandraut]

i love the way how different problems are connected with one another. 01 knapsack problem opened a pandora box for me. thanks to techdose

[bands]

Man your explanations are top notch. I love how you walked through the tabulation solution. it makes so much sense now. Great job

[phuongvy]

For those who has problem with test case [0, 0, 0, 0, 0, 0, 0, 0, 1], target = 1.
According to Mazhar Imam Khan,
The solution doesn't consider presence of "0"s in the array. Why the output is different ?
Because, if we have "0", then, it can have +0 and -0 and still will not effect the sum of a set. For example: Target value is = 2
1) {0, 2} = {+0, 2}, {-0, 2}. Ans: 2
But if we increase number of 0s,
2) {0, 0, 2} = {+0, +0, 2}, {+0, -0, 2}, {-0, +0, 2}, {-0, -0, 2} . Ans: 4

So, if you observe, your answer increase by (2^number of 0s) i.e. pow(2, number of zeros).
So, make a small change as follows:
1) on count of subsetsum function,
if(nums[i-1] > j ) => change to: if (nums[i-1] > j || nums[i-1] == 0)
dp[i][j] = dp[i-1][j];
//make no change and put the previous value as it is in the next subproblem. (I.e. 2, in example above)
And then at the end, you answer will be
return (int)Math.pow(2, number of 0s) * dp[nums.length][target] ;

Also, other cases we need to handle is:
if (S > sum || (sum + S) % 2 != 0){ //S is target

return 0;
}

[renon]

Great video dude, I was able to guess the logic since you have already covered the count subsets problem in this series. Keep going 🔥🔥🔥🔥🔥🔥

[theghostwhowalk]

Great explanation! Thanks.
Here weights were all +. Let’s say if there was similar Qs where weights are -, will DP table work? I think so it will.

Was asked Q like: you can use weights 1, 2, 3, 4 exactly once and find # of combinations to form 5 by add/subtract them. Example: 1+4,

[Cloud-]

I solved the question before I watched how you have solved it all thanks to you. You made dp look easy!! Thank you

[danghuynguyen]

If there are some zeros in the arr like [0, 0, 0, 0, 0, 0, 0, 0, 1], you can solve problem with the same logic.
What you need to do is modify the base case to cover 0 element.
For example: dp[1][0] = 2, [{empty}, {0}],
dp[2][0] = 4, [{empty}, {0}, {0}, {0, 0}], ...

```
dp[0][0] = 1 // empty set
for (int i; i <= arr.len; i++)
{
if arr[i - 1] == 0:
dp[i][0] = 2 * dp[i - 1][0] // Empty subset + subset made by 0 element
else:
dp[i][0] = dp[i - 1][0]
}
```

[crazySeafood]

minor correction, at 3:07, I think the possible subsets can go from (0 to (2^N)-1) because you have 2^N ways to choose a subset.

[avaneeshyadav]

Is it possible to solve the subset sum problem in the case of an unbounded condition? Below is a question(Correct me if I am wrong) that seems to be an unbounded subset sum.
Prob statement- Given a score N and a book with 10 pages counting from 1 to 10. You need to open the book randomly and node down the even number till you get the required score of N. You will have to stop counting if you get 10 or 8. How many ways you can score the required score?
Example- N = 6, Output = 4. score can be [{2.4}, {4, 2}, {6}, {2, 2, 2}]

[poojamalhotra]

Wonderful way of explaining. All of these are super easy after going through your knapsack problem. do you have a video on print subsets with given sum ?
Can't understand from other videos.

[MrThepratik]

The above approach doesnt work for input [0, 0, 0, 0, 0, 0, 0, 0, 1] and T = 1, i believe it only works when you have unique items

[stith_pragya]

Thanks TECH DOSE for this amazing and very very helpful

[learnersparadise]

Bro, a frank advice, have you checked your solution with different inputs? try with [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] and sum = 2, let me know if it works. Dynamic programming is failing here

[MS-rwrh]

last row, colm 1 and 2 might be 1 instead of 2 because colm 1 and colm 2 < last row, which is 3. So we should exclude colm 1 and 2, and make those colms pointing to prev colms.

[bvivekvardhan]

Hello sir,
Thank you for explaining all the problems nicely. Is there any code for this problem? Can you pls share it?

[NinjaChris]

Hello. I was just wondering how you might modify this to produce all the subsets with a given sum. For example, it given the set (1, 2, 3) and the sum 3, how would you output (1, 2) and (3) using this approach. Thanks!

[abhisheksaraf]

It would be great if you cab make few videos on minimax concept and how think about those problem