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:
/ @techdose4u
INSTAGRAM : / surya.pratap.k
SUPPORT OUR WORK: / techdose
LinkedIn: / surya-pratap-kahar-47b...
WEBSITE: techdose.co.in/
TELEGRAM Channel LINK: t.me/codewithT...
TELEGRAM Group LINK: t.me/joinchat/...
=======================================================================
USEFUL LINKS:
Subset Sum Problem: • subset sum problem dyn...
01 Knapsack: • 01 Knapsack using Recu...
01 knapsack Memoization: • 01 Knapsack using Memo...
01 Knapsack Tabulation DP: • 01 Knapsack Tabulation...
#subsetsum #01knapsack #dp

[@JasbirSingh-kp4eu]

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

[@techdose4u]

Nice 😊

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

[@techdose4u]

Welcome :)

[@shilpaaggarwal5008]

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!

[@dayanandraut5660]

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

[@techdose4u]

Great

[@mdlwlmdd2dwd30]

if you want to understand why it is. Try to study topic related to NP-complete and NP-hard. It would give you good insight.

[@100bands]

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

[@275phuongvy]

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

[@techdose4u]

👍🏼

[@janvimahajan8447]

I am just looking for this only. Now I am able to understand target sum leetcode problem. Thanks!

[@PRABHATKUMAR-ek5cu]

I was also searching about this testcase

[@anushkasngh31]

Hi, can you explain why you returned 0 in this condition-> (sum + S) % 2 != 0?

[@yuvrajdeshmukh7157]

@@anushkasngh31 I'm also confused in this. Have you figured it out?

[@renon3359]

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

[@techdose4u]

Nice

[@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, 2+4-1......

[@techdose4u]

This is the target sum problem. I will show this problem soon.

[@Cloud-577]

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

[@danghuynguyen8579]

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

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

[@avaneeshyadav124]

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

[@poojamalhotra8280]

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.

[@techdose4u]

I don't remember 😅

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

[@afzalsiddique7165]

The above approach does not work when you have zeros in the array.
make the following changes:
1.
from this->
if j
if j
return dp[A.size()][t]
to this->
return pow(2,no of zeros in A) * dp[A.size()][t]
The reason is 0 does not affect the target but it affects the count because +0 and -0 is the same thing.

[@bhaveshvarma4313]

@@afzalsiddique7165 Thanks

[@gowthamarun43]

@@afzalsiddique7165 multiply the result by 2^no.of zeros will not work all the times. It works only when there are only leading zeros.
You should modify the 2d matrix while initialization
if(nums[i]==0) dp[i][0] = dp[i-1][0]*2
else dp[i][0] = dp[i-1][0]
Or we can change the 2d tabulation technique by optimizing it into 1d array

[@VarunMittal-viralmutant]

@@gowthamarun43 Can you please expand this comment ? By leading zeroes you meant, not of type [0,1,2,0,3] ?
I think people generally/always sort the input for DP tabulation in ascending order so all 0s will always be leading ?

[@yaswanthharidasu9801]

@@VarunMittal-viralmutant Instead of worrying about zeroes, simply change the following:
from: if(w==0) return 1;
to: if(w==0 && n==0) return 1;

[@stith_pragya]

Thanks TECH DOSE for this amazing and very very helpful video..............🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻

[@learnersparadise7492]

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

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.

[@NguyenucNam_]

Thanks sir, very easy to understand!

[@techdose4u]

Welcome :)

[@bvivekvardhan]

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

[@NinjaChris127]

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!

[@codingessential91]

that will be a question of backtracking with exponential time complexity.

[@abhisheksaraf2616]

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

[@techdose4u]

Sure

[@mdlwlmdd2dwd30]

so when we initialize array we should do dp[arr.size()][sum]??

[@hizmzmhei8824]

Hello sir,
Could you help me in one problem,
"Count the number of ways an array can be divided into two equal halves so that both halves have equal sum." Entries of array are always postive.

[@techdose4u]

Please mention the problem number

[@hizmzmhei8824]

@@techdose4u
It is not on leet code, but I found the problem in competitive hackathon.
Say we have a array [3, 1, 1, 2, 2, 1], we need to divide it into two subsets such that sum is equal. (This much is in one your video).
But the coding ques asked to count such ways.
For above array it would be 2
Which are
1. {3, 2} and {1,1,1,2},
2. {3, 1,1} and { 1, 2, 2}
So answer should be two for this case.
If n is size of array then n goes upto 10^5
And array[i] in [0, 100]

[@kingrajput6202]

this is more or less the same problem actually:
(For integer input)
First u need to check if the given sum is even as only even sum can be divided into two equal integer halves:
Then u use the subset sum algorithm to find how many number of the subset that add to half of the original sum is possible and that will be your answer,

[@yagizegemen7303]

It will in correct output for [0,0,0,0,0,0,0,0,1] and X=1 .Expected =256 and actual =1

[@swetantkumar7029]

This is the problem I am also facing

[@00mrde]

Thanks man for you awesome video.
It seems in your matrix dp[3][1] and dp[3][2] must be written 1.

[@mohantraju]

excellent

[@techdose4u]

Thanks

[@MsJabbari]

Thanks for the great video, but I have problem in handling input [0,0,0,0,0,0,0,0,1] and T = 1.
I tried
if(nums[i-1]==0) {dp[i][0] = dp[i-1][0]*2;}
else {dp[i][0] = dp[i-1][0];}
but the case [7,9,3,8,0,2,4,8,3,9] and T = 0, doesn't pass.
Does anyone have the complete java code for 2d dp the same as the video instruction?

[@shishirarora8808]

You may just sort it and use sliding window, if just a sum exists is needed
Will be o nlog

[@accordlematia8264]

hello, the explanation is awesome, can you write the python version of this code?

[@himmatjinjala4459]

video quality is excellent ☺️👍
and cool

[@syedkaja2045]

amazing!!!
but i cant understand tabulation dp is it necessary to know

[@techdose4u]

Not necessary. But good to know to improve your complexity for some problems.

[@neghatnazir1668]

i feel tabulation is easier thn top down lol!

[@techdose4u]

😅 Everyone has their own taste.

[@syedkaja2045]

@@techdose4u yeah 😀

[@Vikash_Art]

How can we find the minimum size of the subset for which the target sum is achieved.

[@prithvimonangi5080]

subscribed, thanks very much

[@mayurbhat9479]

Sir, is this problem similar to counting number of ways to arrange a coin(coin change) problem?

[@srimanyadagiri7831]

coin change 2 to be precise I think

[@rishviks8987]

Sir this logic is not working when you have zeros in the array

[@MrThepratik]

yes it doesnt work for input like
[0,0,0,0,0,0,0,0,1] , T = 1

[@yadhunandhanr7590]

@@MrThepratik What should be the answer for this ? (0,0,0,0,0,0,0,0,1] , T = 1)

[@amit2197kumar]

@@yadhunandhanr7590 For arr[0 0 0 0 0 0 0 0 1] and T = 1 answer should be 256

[@amansingh.h716]

sir the recusrsion wala part not working properly

[@dameraajay7132]

Sir make vedio on Coin change problem

[@techdose4u]

It will come after 01 knapsack soon

[@vishalgoel6323]

Video*

[@parichayrishi9019]

Will counting the numbers of 'True' in table where the column == sum work? @TECH DOSE

[@digvijayyamagekar4300]

Yeah but the again time complexity is going to increase n*n

[@malikwaseem1983]

Thanks Tech Dose

[@techdose4u]

Welcome :)

[@sanaul5190]

Great job❤️

[@amitp277]

great stuff 👍🏻

[@ronitdhingra4395]

only works for distinct items, For instance this method wont work for an array of 0s and 1s

[@homocode6070]

i watch this video, after i tried to solve leetcode problem "target sum" using dp tabulation, but this wrong ans. please brother help me??

[@prasannakatabattini1974]

can u send the code for this problem..i got wrong an"Could you please provide the code for this problem? I received an incorrect answer."
swer

[@saikumarbandapalli1549]

In the video, second and third column of last row of the dp table was wrong. The values should be 1,1 not 2,2

[@VarunMittal-viralmutant]

Please pardon my naivety, maybe I am dumb :(
Shouldn't this be "count subsequences with sum" instead of "subset" ? I mean, {1,2} and {2,1} are same subsets, right ?

[@ganeshkamath89]

they are differetn subset, assume you have 3 different coins {1,2,1}, then you will understand.

[@rajaryan7566]

Thanks!

[@techdose4u]

Welcome :)

[@d35tr0.]

My gf left me , I was feeling terrible . Just to get her off my head I watched this video . Btw I luv dp .

[@digvijayyamagekar4300]

Ganja mar le bro

[@ismail8973]

When we started studying seriously, at that moment algoexpert ad coming. It's too annoying.

[@techdose4u]

😂

[@srikrishnabejawada3126]

❤

[@naive-fleek7420]

this doesnt works when array contains zeros

[@lucasaraujo6.]

does anybody have the code of this solution?

[@anujsoni9941]

this solution fails when zero is present in the array

[@dineshothamkumar]

I believe n==0 return false must precede w==0 return true

[@gauravbhisikar6381]

not understand this step at 16:16