Dp 16. Partition A Set Into Two Subsets With Minimum Absolute Sum Difference | DP on Subsequences

[@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 ❤✌🏼

[@divyaporwal589]

It is not working with negative numbers, for example the array is -36,36 and then the target is zero

[@harshitrawat138]

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

[@spytonic4171]

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

[@kaushalwaghela429]

understood if possible, please give leetcode and gfg problem links also. thanks :)

[@trendtoyou7967]

We need not calculate minimum repeatedly. Traverse last row in dp array in reverse order and return first true cell.... Total-2*i

[@rishabhsinha7250]

This is the first time when I am able to understand what a DP table looks like in real and how it works. Its a level up for me. ThankU Striver.

[@aryashjain7893]

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.

[@ankitanand1539]

Use long long

[@fettuccine794]

Exactly !!!

[@dhananjaygorain6375]

@@ankitanand1539 still it showing runtime error can you give your code please

[@gamersgame43]

use unordered_set?

[@ganishk3568]

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

[@pratikdas1780]

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.

[@visheshagrawal8676]

it took me 50 mins to solve the question without looking the answer it's all because of you the way you teach.. ✨✨✨✨

[@vikasbagri1225]

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

[@mrsunny8299]

understood, i dont know why i was skipping dp, it is easy, (you made it easy to understand this). Thankyou.

[@vikasgupta6701]

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!!

[@tonyconor681]

exactly

[@pritimurmu7898]

bro how did you solve for negetives

[@prashantpal3510]

me too

[@VedeshPadal-ev9tt]

@@pritimurmu7898 were you able to solve this question on leetcode

[@SahanaaEvan-mo6zv]

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!

[@sakshisakshi5677]

You made the concept clear easily and smoothly🙌

[@sanginigupta1312]

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

[@shreyashtech8556]

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.

[@rohitbadhai8219]

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.

[@VY-zt3ph]

This is the question which I was eagerly waiting for you to upload since the day you uploaded first DP lecture in this playlist.

[@channelname4394]

Best explanation. understood , hope this channel reaches more people

[@GManiKarthik]

Man, what an explanation! This question went from rocket science 🚀 to halwa on a plate 🍰-smooth, logical, and so intuitive I almost feel smarter just listening! 🧠💡 #Understood #DP16 #HatsOff 🎩 #Striver 🙌

[@nikhilprasad644]

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

[@aseem-b23]

Did you come across a solution for the negative numbers?

[@EerieEntertainment-mc4ce]

@@aseem-b23 agar array ka minimum element negative hai to saare element me use add krke array ko non negative banalo

[@manikiran949]

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

[@ramakrishnan4356]

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

[@safiwasif2905]

@@ramakrishnan4356 thx mate

[@mohan_codes]

Amazing! thankyou DSA parasurama striver best teacher ever in my life.

[@anshul5533]

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

[@takeUforward]

True.. concept clear hone se u urself can do these small things :P

[@sparks8754]

Inspiring

[@deepaksarvepalli2344]

I am searching for this comment... satisfied...😂

[@vanshsehgal9475]

Can you explain a lit bit more? I did not clearly get what are you trying to say..

[@abhishekcs5468]

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

[@stith_pragya]

UNDERSTOOD............Thank You So Much for this wonderful video........🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻

[@iamnoob7593]

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.

[@pritikasharma9857]

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

[@amritanand1714]

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?

[@kotipallimadhumeher71]

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.

[@dennyage4791]

What if we have negative integers in an array, then this approach won't work ??

[@codelikebeast3971]

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

[@iamnoob7593]

same i had doubt too abt it now its clear.

[@paridhijain7062]

Understood. Sir, You are really making great efforts for students like us. Thank you for teaching us.

[@JeevanGaikwad-G1]

Understood. Very nicely explained the tough problem in an elegant way. Thanks.

[@udaypratapsingh8923]

you made the concept clear easily and smoothly🙌 : )

[@cyro_-ej6xm]

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 .

[@AquaRegia-i3u]

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.

[@kishorkumarbehera5412]

Can you give me the code for reference ?

[@AquaRegia-i3u]

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

[@AquaRegia-i3u]

@@kishorkumarbehera5412 added the code

[@kishorkumarbehera5412]

@@AquaRegia-i3u 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.

[@RohitKumar-jd7un]

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]

[@ishaanchandak4774]

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

[@shivamdwivedi8120]

In case of negative integers, what should we can do ?

[@VishalGupta-jh9nz]

Just add absolute value of minimum integer to every element

[@avicr4727]

@@VishalGupta-jh9nz can you provide me the code it will be very helpful

[@VishalGupta-jh9nz]

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

[@yogeshlamba5485]

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

[@keshavbaheti7327]

​@@yogeshlamba5485 use long long and guess what 1e7 +1e8 is not equal to 1e9.😊

[@MukeshKumar-cc3uh]

Understood ❤ and thanks for the inspiration by working at 4AM in the morning.

[@aryanbhagat6252]

How do we do this with negative elements as well?

[@himanshujindal1532]

I appreciate the hardwork you putting

[@MohammedAmrath]

Bhayya can you explain how can we handle the negetive cases where -10^7

[@chanchalroy3417]

Just because of the previous lectures I was able to solve this problem without watching this lecture. Take a bow... Understood ❤

[@amritanshusinha9401]

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?

[@cooltomcatty]

Beautiful Explanation!!! Kudos!!

[@shantanu240895]

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.

[@sherlockholmes1605]

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.

[@ihsannuruliman3656]

it would work yeah just check of out of bounds.

[@SR-we1vl]

Can you please share the code!

[@tusharnain6652]

It wont work with negatives, there's a negative number case in leetcode, this solution fails there.

[@jigardoshi2852]

Yes agreed, this DP solution will not work when numbers are negative or 0 or for matter if totalSum of all nums is 0.

[@vinayprakash1687]

Thanks. I feel if I got this question without knowing about previous question (partition equal subset sum), I would solve it differently. 1. Set target = sum(arr)// 2 2. Try to subtract all the array elements such that the target becomes 0 or atleast the distance from 0 is minimum. In other words, try to find maximum sum using the elements such that it is

[@advaitbajaj4241]

Even I thought of the same way but am unable to code it this way. Could you please provide me the code?

[@alessandrocamilleri1239]

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;

[@kushalgupta2041]

An another apporach can be:- We just have to fix the target to the (totalSum/2) and return the minimum difference between the nearest value to the target for example the target we need is 5 and if there exist a sum of 5 then we return 0 means the target is possible and if there exist the closes value nearest to the 5 is 3 then we return 2. Here's my code hope you understand what i did:- int f(int idx, int target, vector &dp, vector &nums){ if(target == 0) return target; if(idx < 0) return target; if(dp[idx][target] != -1) return dp[idx][target]; int notPick = f(idx - 1, target, dp, nums); int pick = 1e9; if(target >= nums[idx]){ pick = f(idx - 1, target - nums[idx], dp, nums); } return dp[idx][target] = min(pick, notPick); } int minSubsetSumDifference(vector& arr, int n) { int sum = 0; for(int i = 0; i < n; i++) sum += arr[i]; vector dp(n, vector(sum / 2 + 1, -1)); int minLeftSum = sum/2 - f(n-1, sum/2, dp, arr); int minRightSum = sum - minLeftSum; return abs(minLeftSum - minRightSum); }

[@bapanmandal9019]

In case of negative integers, what should we can do ,vaiya ?

[@HarshKumar-ip5nr]

substract min(nums.begin(), nums.end()) from each element.

[@surya4193]

thanks striver,I am able to improve my coding skills the main reason is you and your way of teaching

[@krishan_aggarwal9376]

Please make a video regarding neagtive values too 😓. This one understood❤❤

[@harshvardhangupta5323]

wont it be the same logic?

[@sumerrawat6947]

@@harshvardhangupta5323 dp cannot store negetive indexes

[@surajbaranwal56.]

leetcode qn

[@rickk3300]

I also have this same doubt

[@jaycodes6599]

In tabulation there is no need of this condition : arr[0] = 0 Therefore a[0] will be always less than or equal to k

[@guptashashwat]

If array elements are negative what should we do?

[@denishfuletra7863]

let me know if you find ans for negative elements.

[@Swiftie13498]

Understood !This series is just insane.I've never understood dp this much easily.Striver you are god level person.Period.

[@imranimmu4714]

Raj bhaiyya, no one could have taught this better than you, Thank you soo much

[@prajjwalpandey2278]

This can be alternatively solved, if we can find a subsequence with sum closest to totalSum/2. Correct me if I'm wrong.

[@vedanshbhardwaj6548]

ya even I did so, but somehow the space optimised solution went wrong

[@amitmahato6404]

[2,3,7], sum/2=6, closest sum can be 5 or 7

[@vedanshbhardwaj6548]

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

[@amitmahato6404]

@@vedanshbhardwaj6548 yeh, S1=5, SO S2 WILL BE 7, MIN DIFF IS 2

[@ObitoXuchiha942]

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 ❤❤

[@himansh4812]

Yes. Only columns till totalsum/2 is required.

[@hemasaijammana5658]

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

[@pawanagrawal7653]

in which company..?

[@spytonic4171]

do you use recursion??

[@aseem-b23]

As always, great video. Thanks for the explanation Striver. Two points - 1. Rather than finding minimum for every single element, we can run a loop starting from the middle element till 0, and return the first value where dp[n-1][i] == true. 2. How can a problem be solved where the array can contain negative numbers?

[@sumitkumartah2106]

just sort the array

[@adi_7861]

How we can make it work if array contains negative elements as well?

[@anshumansharma2251]

meet in the middle or binary search

[@daniyalhussain5231]

Why cannot I think of such solutions LoL!!!! Amazing Job!!!

[@nitishverma1484]

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]

[@amartyagupta9922]

arr[0]

[@meerapanchal8258]

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)

[@neelulalchandani7429]

thanks this helped.

[@parasjaggi268]

understood i tried earlier i made recursion but wasn't able to make it to dp ,,,,,,,,,thanks for making it easy

[@rohankar5604]

Understood, great explanation !!!

[@prateeksharma3698]

If negative elements are also present in given array then what will be maxSum ?

[@sageoustheory1957]

did u find the ans ?

[@piyushsaxena6243]

understood, thanks for these amazing lectures bhaiya ❤️

[@ShubhamKumar-vp4pu]

Hey striver, I have understood the concept but can we solve it using recursion ?

[@sjsjdsbsjjwjs2659]

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

[@prakharsoni7621]

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 :)

[@harisrashid0773]

yes we can but will give tle ;

[@hashcodez757]

"UNDERSTOOD BHAIYA!!"

[@Pavankumar-ck5ot]

Understood. I think if we declare dp array of size [n][total sum/2+1] will also work.

[@takeUforward]

Yes works

[@dharmeshpoladiya9047]

Understood 💯💯 Great Explanation. Thank you very much for all you efforts🔥🔥

[@sannareddymonesh7598]

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

[@balakrishnanr648]

in LC its that way

[@softwarefoodiee]

Sum cannot be negative sunce its mentioned that all the elements are non-negative.

[@vinaykumarratnala5832]

I have solved this question before watching this video only based on the concepts applied in all prev videos. thank you so much

[@PANKAJKUMAR-oy1hh]

i solved by finding value closer or equal to the half of total sum. but, i feel ur approach is more clear and concise.

[@sameerbilla515]

I did same, but cannot memoize it.. can you please tell how can I memoize it

[@saddy4420]

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.

[@maneeshapanu]

This code now is giving tle with one test case.

[@vedantojha766]

Yes

[@atmaramkambli7800]

1st half of video, I was like why we're learning subset equal to k tabulation, 2nd half of video, I am saying "The Legend Striver"

[@jeet7000]

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

[@shadab9764]

Thanks man!

[@parthsalat]

Understood Kaka! Enjoy your stay at Warsaw!

[@TheProblemSolvers38]

comeeeeeeeeeeeeeeeeeeeeeeeeeeeee ooooooonnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnn striverrrrrrrrrrrrrrrrrr...................You are tooo amazing to be on this planet Earth ... How can someone on earth can explain such complex solutions sooooooo easily................ come on .......... I just can't believe this...............

[@rishabhgupta9846]

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

[@cinime]

Understood! Thank you so much for the amazing explanation!!!

[@rutwikmore7462]

Explained beautifully ♥

[@ankitkamat4442]

I don't know if sweet or not, but this question become a good looking halwa!! Great explanation!!!😍😍😍

[@chamanjain9843]

28:22 line no 9 if(arr[0]

[@harshpratapsingh1638]

you really make this question a piece of cake

[@pranchalsharma2647]

We need to look at the constraints here because this only works for positive integer array and not when negative numbers are in the array.

[@_ArjitKhare]

Amazing Turned a question into a tool

[@abhijeetmishra3804]

UnderStood Bhaiya ...u are a genius ...but the only problem i face is how to use this logic during exam...not able to guess the logic.... But the answer is PRACTICE PRACTICE AND PRACTICE >>>>

[@rajsekhardutta8891]

Amaazing explanation! Understood!🤩❤

[@madhurgupta4220]

Very Good Explanation. Understood. I think this will be more than enough

[@lakshmipriyarajannagari9764]

Understood Bro! Hats off to your dedication ...we can learn lots and lots of dedication , determination ,passion , discipline and everything from you ❤❤

[@sangeethagopalan301]

Greatly simplified!! Understood!!!!

[@sahilbadkul7130]

Understood man, grt explanation make every hard concept as easy as you can. then there is not something like difficult. 😇

[@gnanaphanideep6398]

understood! Thank you for the explanation.

[@ntgrn-pr5yx]

understood , thank you striver

[@paveshkanungo6338]

Understood! Thank you Striver

[@tanazshaik678]

2 mins of silence for how my brain just stopped in shock when solved this hard problem in a way that my mind processed.

[@kathanvakharia]

Understood...Completed 16/56

[@jaydevkundu554]

Able to solve with just starting hints of 5min.. Thank you striver.. ❣

[@Rahul-ls4ju]

Understood. Another approach which I thought was to find S1 such that it is nearest to totalsum/2. THis could be done by map or simply by loop. Then could find S2 and hence S2-S1

[@riyakumari8377]

i thought of same but cant code it properly! :(

[@xyz956]

​@@riyakumari8377 int rec(vector &arr, vector &bucket, int index, int sum) { if (bucket.size() == arr.size()/2) { // for ( int i =0 ; i

[@zeppelinpage861]

Absolutely brilliant!!! Thanks a lot

[@shauryatomer1058]

thanks again for this awesome tutorial

[@abhishekjhanji3014]

"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

[@AmanKumar-fl5ws]

was looking for this !!

[@ranasauravsingh]

UNDERSTOOD... ! Thanks striver for the video... :)

[@arpnasjs9825]

Understood Thanks for this amazing series