Minimum subset sum difference | Minimum difference subsets | Dynamic Programming
ฝัง
- เผยแพร่เมื่อ 19 ต.ค. 2020
- This video explains a very important programming interview problem based on dynamic programming in the 01 knapsack category which is to find the minimum subset sum difference.In this problem we need to minimize the difference of sum between 2 subsets which are formed on dividing a set into 2 subsets.The sum 0 will be minimum for all positive numbers when equal sum partition is possible.This problem is very similar to the equal sum partition problem and uses the subset sum problem technique with a little tweak to solve the problem.I have first explained the problem and then showed the intuition by reducing and relating this problem to the already solved subset sum problem.I have shown examples for better understanding and intuition and at the end of the video, I have also shown the code implementation in both Java and C++.
CODE LINK is present below as usual. 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/codewithTECHDOSE
TELEGRAM Group LINK: t.me/joinchat/SRVOIxWR4sRIVv5...
=======================================================================
CODE LINK: gist.github.com/SuryaPratapK/...
JAVA Code: gist.github.com/SuryaPratapK/...
USEFUL LINKS:
Subset Sum Problem: • subset sum problem dyn...
01 Knapsack Tabulation DP: • 01 Knapsack Tabulation...
Equal Sum Partition: • Partition equal subset...
Count Subsets with given Sum: • Count subsets with giv...
#dp #subsetsum #01knapsack
What if negative elements are there?
Firstly, thank you so much for doing these videos. Much appreciated!
Question:
Set S is divided to S1, S2. We are calculating only for S1, which is
yes, by taking dp[n+1][sum/2+1] we can reduce the time complexity. I guess he just wanted to explain in a way everyone understands the concept behind it and that's why he took dp[n+1][sum]
Thanks! Very well explained. Knowledge of solving 'Subset sum' (links in desc) is a pre-req for this.
You have a great voice which makes us pay detail attention to what you're saying . Thank you for such excellent series. Very engaging!
Looks like I should apply for singing 😂
@Andrew Kaison HAHAHA
It was so good, I slept while listening to him,
@pooja gattiga chaduvtav.
We can reduce time by creating a dp[n+1][sum/2+1]. Thanks sir, it worked because u explained so well.
Nice 👍🏼
Yes I did it that way too. All thanks goes to sir.
@@suvamroy6205 👍🏼
I was thinking the same thing @Aditya Ohja
We can also iterate from backwards i.e. for(int i = sum/2 ; i>=0 ;i--) in the last step.
great work sir. for all your videos, before watching till the end, i hit like cz i know it will be awesome and simple to understand : )
a small optimization, instead of constructing N*W array its enough to construct N*ceil(W/2) and check last row from last column and if it's true then min-difference=abs(i-(W-i)) where i is the column index, W is sum, happy coding :)
That's what I wanted
sir, one thing i didn't understand, we are checking for dp[n][i]==True condition , how can one be sure that dp[n][sum-i] will also be true??
Thanks for the clarifications and the code example!
I first got the wrong value, but I did a mistake , if I want to get the two optimal pair of values then I need the "i" value instead of diff, or you can return both the i and diff.
I use PHP, so it will be:
$value = 0;
for ($i=0; $i abs($first-$second)){
//get value
$value = $i;
$diff = abs($first-$second);
}
}
return [
'value' => $value,
'diff' => $diff,
];
Nailed it sir 🔥🔥🔥
extraordinary explanation. Keep it up, mate.
What about an array of negative and positive integers. Would dp be able to solve this efficiently?
Since we are considering that s1 < s2, will it make sense instead of taking the weight range 0 - 11, we just take 0 - 5? Since it seems that at the end we will use the last for column 0 - 5 only?
You are absolutely correct. It would reduce the space complexity as well as the time complexity to half of the original and of course it would still work.
Yes.... you are correct.
This idea came to me too. Was just about to ask and verify
@@avinashjha4887 Space Complexity wont decrease but space will decrease
thank you so much sir for such a great explanation...really it was very much helpful thanks a lot sir...
So if we want to solve this question using recursion then we have to apply subset sum solution for 0 to sum/2 and then we have to find the minimum of them after putting them in this formula:- (sum - 2(answer of each subset sum problem))?
Great explaination sir
Thank You
Welcome :)
Thank you for the video. For some reason, this code does not work for some inputs like: [76,8,45,20,74,84,28,1]
Thanks for video! I guess it’s tricky to see this as a variation of can we divide the array into 2 equal sum subset question.
Welcome
Thanks for video..osssum
Great work!!!!!!!!!
In the code when you try to find the minimum difference value, you iterate from 0 to sum/2. I its not always the result in the True value that is closest to the sum/2 ?
i= sum//2
while not dp[n][i]:
i-=1
diff= sum-2*i
if i is closer to sum/2 the difference is minimized, therefore we only neet to find the column with True value closer to sum/2.
fantastic explanation
It is not one of the best explanation, but it is the best explanation. Thank you🙏
Thanks for the appreciation :)
hey your code is not working on leetcode
def minimumDifference(self, nums) :
n = len(nums)
sum = 0
for i in range(n):
sum += nums[i]
dp = [[False]*(sum+1) for i in range(n+1)]
for i in range(n+1):
for j in range(sum+1):
if j == 0:
dp[i][j] = True
elif i == 0:
dp[i][j] = False
elif nums[i-1]>j:
dp[i][j] = dp[i-1][j]
else:
dp[i][j] = dp[i-1][j] or dp[i-1][j-nums[i-1]]
diff = float('inf')
for i in range(sum//2+1):
first = i
second = sum-i
if dp[n][i] == True and diff>abs(first-second):
diff = abs(first-second)
return diff
you know you've been watching too many tech dose videos when you know the answer the moment he says "it's a variation of ... problem". LOL thanks
how deal if array has negative elements
sir u are great....continue
Sure :)
if nums[i] is negative then how to proceed?..in the leetode qn constraint its negative
Hi Sir, What if the input contains negative numbers too? I see the solution would not consider negative number in the input array
Exactly what I am trying to find the solution for, I guess in Negative numbers we cant really use this approach
You can use 1D array to do that, no need for 2D tho.
Yea :)
How do you go back and look up the true/false values?
Can you link to any example of this?
@@nemnoton Just iterate over the last row, by keeping row no. constant.
sir,you have explained diff=sum-2s1
but in the code abs(first-second)
can we use any of the above statements?
and overall amazing explanation
In the code I have simplified. If you closely look at first and second then first is S1 and second is (SUM-S1). If you subtract them then it will be (SUM-2*S1). They both are exactly the same.
@@techdose4u thanks sir
Welcome
this approach is not working for negative numbers
Good one!
Keep it up
Thanks 😊
In case of negative values it will fail as array can not have negative index.
19th line:
What if (j - A[i] < 0)?
We'd get a Segmentation Fault;
Firstly thank you very much for this whole DP series. It is extremely helpful. Secondly, I have a small doubt. If I know that my subset S1 can have maximum sum as S/2 only, I can find the maximum sum S1 can have(like max profit in 0/1 knapsack). In that case we will store max sum possible and not T/F in the DP table. Is this approach fine? I solved the interview bit problem like this, but wanted to know from you if thinking this way is fine too
Yes. You can store the max amount. Perfectly fine :)
@@techdose4u Thank you :D
Your code will set false at dp[0][0] which is not right , according to the theory part
Can you try adding serial numbers to this dp series and make a playlist?
Thanks 👍🏻
It's already in the playlist and numbering will hamper me from adding new videos randomly and shuffling part. Moreover, those who want to learn just particular videos will not feel comfortable if I number them.
@@techdose4u okay, thanks bro 👍🏻
@@techdose4u I have a suggestion: Instead of numbering, you can categorize them into DP patterns. e.g. ks-01 from knapsack 0/1, ks-INF (knapsack infinity), Partition (e.g. MCM, eggdrop), etc. so that students can see the similarity in code within a given pattern. Thanks!
@@0anant0 yea. That I am doing. I am covering in order and later when I include more videos then I will insert them in order.
@@techdose4u Thanks! Your videos are very helpful - I watch them everyday :-)
bro, can we do it using int[][] dp not by boolean[][] dp??
Yep
@@techdose4u can you please explain it little bit.
You can use short array as well treat 0 as false and 1 as true. Also we can optimise the solution using 1D tabular dp just like sunset sum. Also solving only till sum/2 is enough
What if S1 is found after half ?
S1 represents the smaller partition so it has to be
can we fill the dp table using recursion
That's memoization.
@@techdose4u yes pls explain this method or else just type the code
@@techdose4u pls just type the code sir please :(
@@techdose4u why are u not replying sir
bro what if the numbers are negative
How this is different from leetcode 2035 ?
Leetcode 2035 : Partition array into two arrays to minimize the difference
why this code gives runtime error-class Solution {
public:
int minimumDifference(vector& nums) {
int sum=0;
int n=nums.size();
for(int it:nums){
sum+=it;
}
vectordp(n+2,vector(sum+2));
for(int i=0;i
man , why do you waste others time by putting the solution that doesnt work?? check on leet code, the -36,36 test case is not working
Please make a roadmap for fresher (batch 2020)to crack google in 6months for a DSA beginner