Number of subsets with given difference | Dynamic Programming | 01 Knapsack
ฝัง
- เผยแพร่เมื่อ 5 ก.ย. 2024
- 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:
/ @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:
Count subsets with given sum: • Count subsets with giv...
Subset Sum Problem: • subset sum problem dyn...
Equal Sum Partition Problem: • Partition equal subset...
Minimum Subset Sum Difference: • Minimum subset sum dif...
#dp #01knapsack #subset
Earlier it used to be a difficult problem for me but you converted it into a cakewalk. Thanks, Sir.
Welcome 🤗
holy crap your video is the simplest but the best
Thanks :)
Liked the way you transformed the problem into standard problem.
I am learning this alot from you 😊
Thanks
Did you ever thought about advertising your channel? I am thankful that I found this channel.
Nope. Never thought of advertising myself or promoting other products. I depend on word of mouth :)
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 🙏👍
Welcome bro :)
Damn! that was so nicely explained. 🤯🤯🤯🤯🤯🤯
Thanks 😊
the way you approach a problem is really awesome sir.. learning a lot from u sir... even though late,,, better late than never : )
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 ?
the (diff + sum) / 2 comes out to be 5.5 to be exact, which is not possible in this array, i.e. there cannot be two subsets whose difference of sum gives 5.5
This is an edge case which is not explained here.
If possible please give links to the practice problems in all upcoming videos .
Thanks anyways for making great efforts !
Okay I will try
Watch love babbar's final dsa sheet video
Nice Explanation
Thanks
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
if sum+k / 2 wil come out to be odd number then we just have to return value zero
Can you please provide the question's link, on GFG, Leetcode, ? where we can solve it
I will try
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.
Depends on the requirement of question. They can be different because you should have 0/1 property for forming a subset. Each subset should have atleast 1 element unique. This is the criteria. It doesn't matter what the value of that element is. In above example, Ansawer is 2 because there are 2 possible ways to choose even though values are same.
@@techdose4u Then what if the array is {3, 4, 7} and diff to be found is 0. So, here even though the subsets can only be {3, 4} and {7} but we get the output as 2. Cause at first it counts s1 as {3, 4} and s2 as {7} and the next time it counts s1 as {7} and s2 as {3, 4}
Awesomeeeeeeeeeeeeeeeeeeeeeeeeeeeee ! 👍
:)
you have einstein brain !!
I am just a commoner 😅
Love you bhaiya!!
Thanks
Great explanation bro 👍
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??
Please add link to the problem in description.
Sure
where can I solve this question
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.
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?
i dont know if you need this still but you would want to find subsets that would add up to 4, a value that you can get using the formula he derives in the video
bawa..u r beautiful
Thanks
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❤️❤️.
bro have you figure out that prblem ?
problem link??