Number of subsets with given difference | Dynamic Programming | 01 Knapsack

This video explains a very important dynamic programming interview problem which is to find the number of subsets with given difference.It is a variation of 01 knapsack problem and also a variation of subset sum problem.In this problem, given a set of elements, we are required to find the number of ways in which we can divide the set into 2 subsets so that the difference of their sum value is equal to the given difference.This problem can be converted to a much simpler problem of finding the number of ways to form a subset with given sum.I have shown the conversion of the problem with intuition and example.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:

#dp #01knapsack #subset

[rishabhshukla]

Earlier it used to be a difficult problem for me but you converted it into a cakewalk. Thanks, Sir.

[Sky-nthy]

holy crap your video is the simplest but the best

[rohanseth]

Liked the way you transformed the problem into standard problem.
I am learning this alot from you 😊

[mwshubham]

Did you ever thought about advertising your channel? I am thankful that I found this channel.

[sandeepnallala]

the way you approach a problem is really awesome sir.. learning a lot from u sir... even though late, , , better late than never : )

[renon]

Damn! that was so nicely explained. 🤯🤯🤯🤯🤯🤯

[nihanthgajam]

Consider the test case, arr = [3, 1, 2, 3], diff = 2
According to the formula, i.e (diff+sum)/2 -> target sum will be "5"
and output will be "2"
while actual output should be "0". Can you please explain ?

[TheAjit]

Awesome content and videos bro. I like your explanation very much, the speed of explanation and writing is truly funtastic. thank you for your channel 🙏👍

[atulmalakar]

If possible please give links to the practice problems in all upcoming videos .
Thanks anyways for making great efforts !

[singhalss]

Can you please provide the question's link, on GFG, Leetcode, ? where we can solve it

[AvinashKumar-fbfb]

Hi, sir how can we use this approach to find 2 set(partition array in 2 group) whose product of sum will give the maximum possible product, please let me know??

[saikumarbandapalli]

Please add link to the problem in description.

[sayantaniguha]

Sir, may I know what is the output for the following test-case?
I/P : {1, 1, 1, 1, 1} ; diff=3
?

Could you explain the output?

[Man_of_Culture.]

We can also add one condition, if total sum is odd then we can find only odd difference between two set and if total sum is even then we can find only even difference between two sets

[lucasaraujo.]

You have fixed the values of the sum. It was not suposed to be tha t way. If the numbers were 4, 5, 6 and 12, target 3, how would it be resolved? Your method wouldn't take care of this situation.

[parmarpiyushmantilal]

if sum+k / 2 wil come out to be odd number then we just have to return value zero

[manikantabandla]

Additional Note :
When the "diff" is 0, then unique ways of partitions are half of count of subsets rather than total.
Because when diff=0, then
s1-s2=0 -> s1=s2 and every 2 different subsets of sum s1 account as 1 partition.
Ex: [3, 3] diff =0
Subsets of sum 6/2=3 are
Subset Remaining
[0] [1]
[1] [0]
comes out as 2 but actually only one partition.

[Magiiciian]

What if the (sum+diff) comes out to be odd? I got stuck here... Thinking will it work?🤔
Btw love your work and effort #much_love❤️❤️.