Dp 16. Partition A Set Into Two Subsets With Minimum Absolute Sum Difference | DP on Subsequences
ฝัง
- เผยแพร่เมื่อ 2 ก.พ. 2022
- Lecture Notes/C++/Java Codes: takeuforward.org/dynamic-prog...
Problem Link: bit.ly/3t62bqQ
Pre-req for this Series: • Re 1. Introduction to ...
a
Make sure to join our telegram group for discussions: linktr.ee/takeUforward
Full Playlist: • Striver's Dynamic Prog...
In this video, we solve the problem of Partition a set into two subsets such that the difference of subset sums is minimum. This problem is the third problem on DP on Subsequences Pattern. Please watch DP 14 before watching this.
If you have not yet checked our SDE sheet, you should definitely do it: takeuforward.org/interviews/s...
You can also get in touch with me at my social handles: linktr.ee/takeUforward
I need your support, and you can do that by giving me a like, and commenting "understood" if I was able to explain you.
Keeping a like target of 500 ❤✌🏼
It is not working with negative numbers, for example the array is -36,36 and then the target is zero
@@divyaporwal589 Dp requires array and array can't have negative indexes. If array contains negative numbers you can subtract the most negative number of given array (minx) from every element array so the all the elements will be positive.
@@harshitrawat138 truee but the problems comes when there is a random so if we check for negetive numbers at starting and find diff with each number the we can return it other wise we can continue this algo nice idea
understood
if possible, please give leetcode and gfg problem links also.
thanks :)
We need not calculate minimum repeatedly. Traverse last row in dp array in reverse order and return first true cell.... Total-2*i
understood, but the leetcode question mentioned in the sheet requires meet in the middle approach as it has got negative values, and tabulation fails in this case.
Use long long
Exactly !!!
@@ankitanand1539 still it showing runtime error can you give your code please
use unordered_set?
@aryadhjain7893 that is not an issue if you have initial offset of 10⁷. But the problem is requires both the partitions should be of equal size.
Understood it very well
Thanks for this amazing series
You really are contributing a lot to this community
Best DP series in the whole youtube
You made the concept clear easily and smoothly🙌
I could do the memoized version on my own, but could never do it the bottom-up way. today, i can say that it's clear. and it was damn simple. just checking the sums my array of size n can produce. amazing insight.
bro this problem work only for +ve numbers and not on negative numbers. pls do make a follow up for negative numbers as well, as it might come up in an interview. good companies do ask such.
thanks
Did you come across a solution for the negative numbers?
@@user-hz2nh8kg6x agar array ka minimum element negative hai to saare element me use add krke array ko non negative banalo
Hey did you find a dp solution for negative numbers ? , I have seen in leetcode that it is unsolvable with dp for negative numbers .Thanks
Instead of storing in array store the same in map create map where you can store corresponding sum for values this way we can handle negatives also
@@ramakrishnan4356 thx mate
Understood! Striver you are just brilliant. Your explanation and these concepts are blowing my mind off! Damn I got lucky coz i found a teacher like you! Thank you so much!
Able to solve this problem without seeing the video and using concepts learned in past two videos. That's the power of striver's lectures. Thanks!!
exactly
bro how did you solve for negetives
me too
Was able to solve this in a single go, thank you striver bhaiya, only because of these videos I'm able to develop an intuition in DP problems
This is the question which I was eagerly waiting for you to upload since the day you uploaded first DP lecture in this playlist.
Understood. Very nicely explained the tough problem in an elegant way. Thanks.
you made the concept clear easily and smoothly🙌 : )
Best explanation. understood , hope this channel reaches more people
it took me 50 mins to solve the question without looking the answer it's all because of you the way you teach.. ✨✨✨✨
Dude, really thankful to you man. I solved this question and 95% of the previous questions on my own. the reason is you. your explanation is out of the world. thanx again. hope we meet in person in the near future.
Understood 💯💯 Great Explanation. Thank you very much for all you efforts🔥🔥
Quick Tip 💡: If you want to solve this using memoization, you need to make sure that you call the recursive function for all possible targets. For example let the sum = 10, so target = 5. Now if you call function for 5 i.e. F(n,5) it may not always fill the complete dp grid. So you have to call all F(n,5) F(n,4) .... F(n,0) to make sure all dp[i][j] are filled.
This won't affect the time complexity as if it was previously calculated it won't be calculated again due to memoization.
In tabulation we go from 0 -> n, filling all dp[i][j] no matter what, so in that case it all indexes are filled.
Can you give me the code for reference ?
public class Solution {
public static int minSubsetSumDifference(int[] arr, int n) {
int sum = 0;
for(int num : arr)
sum += num;
int k = sum/2;
if(n==1)
return arr[0];
if(k==0)
return 0;
Boolean[][] dp = new Boolean[n][k+1];
for(int i=k; i>=0; i--)
find(arr, i, n-1, dp);
for(int i=k; i>=0; i--){
if(dp[n-1][i]!=null && dp[n-1][i])
return sum - (2*i);
}
return -1;
}
private static boolean find(int[] arr, int k, int i, Boolean[][] dp){
if(k==0)
return true;
if(i
@@kishorkumarbehera5412 added the code
@@user-ie8sy7wo4m Instead of calling for each target we can call it for sum/2. So when we are picking and not picking we have the sum of the subset, so we can store the difference between the subset sum and the target which is total sum/2, and taking minimum of all subsets. So when returning the final answer we should check if the total sum is even or odd. Accordingly the answer would be 2*ans or 2*ans+1.
code for this approach
bool helper(int ind,int k,vector &arr,vector &dp)
{
if(k==0)
{
return true;
}
if(ind==0)
{
if(arr[ind]==k)
{
return true;
}
else
return false;
}
if(dp[ind][k]!=-1)
{
return dp[ind][k];
}
bool nottake=helper(ind-1,k,arr,dp);
bool take=false;
if(arr[ind]
We can optimize space complexity here since maximum value a subset can take for minimum absolute difference is total_sum/2 so we can make 2d vector for total_sum/2 instead of total_sum and then iterate last row of vector from last col and the first cell with true will be subset1.
kudos striver, you are the reason i got my confidence back , thanku so much , appreciate all the hard work you do , it changes life of thousands .
understood, i dont know why i was skipping dp,
it is easy, (you made it easy to understand this).
Thankyou.
Understood. Sir, You are really making great efforts for students like us. Thank you for teaching us.
Great video. I simplified the minimum subset difference as follows:
int i = totSum / 2;
while (!dp[i]) i- -; // will not go out of bounds since i always stops at dp[0] which is always true
return (totSum - i) - i;
thanks striver,I am able to improve my coding skills the main reason is you and your way of teaching
Awesome Striver , I was confused in how dp vector is formed step by step and what does it signifies, you cleared it with so much clearity . Respect
same i had doubt too abt it now its clear.
Striver bhaiya i think it can be further optimized in terms of time and space if we take our sum as sum/2 initially (as we have taken in DP-15), then the TC : N * (k/2) and SC : (k/2) because we are just bothered about S1 till k/2
True.. concept clear hone se u urself can do these small things :P
Inspiring
I am searching for this comment... satisfied...😂
Can you explain a lit bit more? I did not clearly get what are you trying to say..
@@vanshsehgal9475
You basically try to find target as upperbound of sum/2 and optimize for closest. Here is the memoized solution without space optimization.
---------------------------------------------------------------------------------------------------------------------------
int dfs(int ind, int upperBound, vector& nums, vector& dp){
if(ind > nums.size() - 1) return 0;
if(dp[ind][upperBound] != -1) return dp[ind][upperBound];
int notTaken = dfs(ind + 1, upperBound, nums, dp);
int taken = -1e8;
if(nums[ind]
This is the same question I was asked in yesterday's interview. I came with recursive and then tried of memoization.
After memoization it is giving me TLE, now I am watching this video
in which company..?
do you use recursion??
I appreciate the hardwork you putting
i found this one a bit harder than the previous ones but gave time watching video and doing it by myself and understood it . great work man . n
What if we have negative integers in an array, then this approach won't work ??
For those who are having 49/50 testcase passing on coding ninjas iterate the inner loop upto target/2 and while calculating minimum absolute difference, iterate loop from target/2 to 0 and as soon as you get first true value break the loop (maximum the target value when dp[n-1][target] is true , minimum the absolute difference)
thanks this helped.
Understood bhaiya!! In short we can say that the dp table last row defines whether the target value is possible from given array or not.Then all possible target values are derived from the dp table and we can take min diff among the all abs diff.
Bhayya can you explain how can we handle the negetive cases where -10^7
How do we do this with negative elements as well?
Understood! Thank you so much for the amazing explanation!!!
understood, thanks for these amazing lectures bhaiya ❤️
Hey bro!
Great video and explanation!
Just had a small question. How would you approach a similar problem where the sizes of both the partitioned subsets must be equal?
Amazingly explained!. But I had a doubt won't this method fail if we have negative elements in the given array ? Could you explain this too
Yeah it's a problem. I think we cannot solve then through this way. There are questions on leetcode with negative values. Anyone please reply if they have any solution for this?
understood,able to solve by my own .What I was doing is calling memoization for every subset sum s1 which is giving me TLE. But using tabulation we don't need to call memoization again and again and can solve in one go
Very Good Explanation. Understood. I think this will be more than enough
In case of negative integers, what should we can do ,vaiya ?
substract min(nums.begin(), nums.end()) from each element.
In case of negative integers, what should we can do ?
Just add absolute value of minimum integer to every element
@@VishalGupta-jh9nz can you provide me the code it will be very helpful
@@avicr4727 Yes, I can provide but it gives TLE
class Solution {
public:
int f(int ind, int target, int sum, int size,vector& nums, int n,vector&dp ){
if(ind==-1 && size==n/2){
return abs(target-2*sum);
}
if(ind==-1 || size>n/2){
return 1e8;
}
if(dp[sum][size]!=-1)return dp[sum][size];
int notTake = f(ind-1,target,sum,size,nums,n,dp);
int take = f(ind-1,target,sum+nums[ind],size+1,nums,n,dp);
return dp[sum][size] = min(take,notTake);
}
int minimumDifference(vector& nums) {
int n = nums.size();
int mini = 0;
for(int i=0;i
@@VishalGupta-jh9nz Consider an array , arr = [-1e7, 4, 7, 1e8, 6]
The minimum number here is -1e7, and if go for adding this to all elements, adding it to 1e8 will be out of INT_MAX.
@@yogeshlamba5485 use long long and guess what 1e7 +1e8 is not equal to 1e9.😊
Raj bhaiyya, no one could have taught this better than you,
Thank you soo much
Absolutely brilliant!!! Thanks a lot
Please make a video regarding neagtive values too 😓. This one understood❤❤
wont it be the same logic?
@@harshvardhangupta5323 dp cannot store negetive indexes
leetcode qn
I also have this same doubt
How would you handle this problem in case the numbers in an array are negative or zero too? The tabulation wouldn't work in such a scenario.
It would right? if we add an extra check to see if the index is going out of bounds for dp[i-1]th row.
it would work yeah just check of out of bounds.
Can you please share the code!
It wont work with negatives, there's a negative number case in leetcode, this solution fails there.
Yes agreed, this DP solution will not work when numbers are negative or 0 or for matter if totalSum of all nums is 0.
Understood man, grt explanation make every hard concept as easy as you can.
then there is not something like difficult.
😇
I have solved this question before watching this video only based on the concepts applied in all prev videos. thank you so much
This can be alternatively solved, if we can find a subsequence with sum closest to
totalSum/2.
Correct me if I'm wrong.
ya even I did so, but somehow the space optimised solution went wrong
[2,3,7], sum/2=6, closest sum can be 5 or 7
@@amitmahato6404 ya but the catch is we will only check till totalSum/2....because if one is say 5, other is bound to be 7 so why check for anything greater than the totalSum/2
@@vedanshbhardwaj6548 yeh, S1=5, SO S2 WILL BE 7, MIN DIFF IS 2
If array elements are negative what should we do?
let me know if you find ans for negative elements.
Understood ❤ and thanks for the inspiration by working at 4AM in the morning.
Amazing! thankyou DSA parasurama striver
best teacher ever in my life.
understood i tried earlier i made recursion but wasn't able to make it to dp ,,,,,,,,,thanks for making it easy
Understood.
I think if we declare dp array of size [n][total sum/2+1] will also work.
Yes works
Amaazing explanation! Understood!🤩❤
Understood
Thanks for this amazing series
This problem is entirely depending upon the total sum of array . What if the total sum of array is negative. Then we cannot create negative size dp array
in LC its that way
Sum cannot be negative sunce its mentioned that all the elements are non-negative.
If negative elements are also present in given array then what will be maxSum ?
did u find the ans
?
"Understood" ....Guess what I coded this problem with a different approach and my score is 100 in this problem of """DP""" ....It's amazing to solve DP ..Thanks bhaiya ....
My code here using memoization..
int findans(int a,int t_sum,vector&arr,int i,int &min_v,vector&dp){
if(i
was looking for this !!
Explained beautifully ♥
UNDERSTOOD... !
Thanks striver for the video... :)
Its a suggestion, If you could explain the need of the array as you explained it in this video , in DP-14 video , as I was very confused as to what those T/F represent till end. Now it gets cleared here. I have traced the whole array for that and also that arr[0]
arr[0]
How we can make it work if array contains negative elements as well?
meet in the middle or binary search
@@anshumansharma2251 can you explain why not for negative numbers
I mean cant we use Hash Map or something?
Understood! Thank you Striver
In the first block of for loops, we don't need to check the target until the total sum. we can check target until totalSum / 2 if total sum even or totalSum/ 2 + 1 if totalSum is odd.
Hey striver, I have understood the concept but can we solve it using recursion ?
public class Solution {
public static int minSubsetSumDifference(int[] nums, int n) {
// Write your code here.
int sum=0;
for(int x:nums) sum+=x;
int res=Integer.MAX_VALUE;
for(int i=0;i
Yes by adding this...
for(int i=s;i>=0;i--)
f(dp,n-1,i,arr);
Your dp Array now fill perform the operation now :)
yes we can but will give tle ;
here's my recursive solution
class Solution{
public:
int ans=1e8;
int solve(int i,int arr[],int sum,int curr,int n,vector& dp){
if(i==n){
ans=min(ans,abs(curr-sum));
return ans;
}
if(sum
Thanks man!
great solution , thanks striver
UNDERSTOOD............Thank You So Much for this wonderful video........🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
man i just dont understand how is he able to do video recording at freakin 4 AM in the morning , Very few match that level of hardwork.
This code now is giving tle with one test case.
Yes
i solved by finding value closer or equal to the half of total sum. but, i feel ur approach is more clear and concise.
I did same, but cannot memoize it.. can you please tell how can I memoize it
You made this really easy! Thanks
you are amazing teacher!
understood it clearly. Thank you so much
Greatly simplified!! Understood!!!!
Understood 💯💯 Great Explanation.
Understood, sir. Thank you very much.
great idea of using tabulation of subset traget in finding ,minimum difference between sum of subets (crux: just we need is every possible target sum made by at least some subset or not )
understood sir, thanks for making this so easy.
God level explanation and content ❤🔥🔥
Able to solve with just starting hints of 5min..
Thank you striver..
❣
thank you so much for your hard work
understood ..........thanks for doing gret work sir
Thanks for knowledge, sir!
beautifully explained.
you really make this question a piece of cake
Awesome Explanation. Understood.
understood clear as crystal :))
Understood bhaiys. Thank you so much for your free and amazing content. :)
Understood! Thank you so much!
understood sir!! thank you so much!
Understood
Thank you
US :)
was trying to solve this question by myself but failed but once you said what dp[i][j] represent I immediately understood everything and solved it.
Just because of the previous lectures I was able to solve this problem without watching this lecture. Take a bow...
Understood ❤
Very much Intuitive ✨
Really appreciating work , your way of explanation🔥 , loved it bhai
Understood, thank you.
We can have only sum/2+1 columns in our DP array. It also worked else it was giving TLE for 1 case. Love this playlist ❤❤
Yes. Only columns till totalsum/2 is required.
Understood! Thank you!
u r doing good work brother😌
This was pure gold.