Partition equal subset sum | Equal sum partition | Dynamic Programming | Leetcode

This video explains a very important 01 knapsack dynamic programming problem which is the equal sum partition problem.In this problem, given a set, we are required to divide it into 2 subsets such that their sum are equal.This is similar to 01 knapsack problem and exactly similar to subset sum problem.I have shown the similarity between this problem and 01 knapsack as well as subset sum problem.I have also shown the intuition for solving this problem and at the end I have shown the code using memoization as well as tabulation dynamic programming.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/codewithT...
TELEGRAM Group LINK: t.me/joinchat/...
=======================================================================
CODE LINK: gist.github.co...
USEFUL LINKS:
Subset Sum Problem: • subset sum problem dyn...
01 Knapsack Recursion: • 01 Knapsack using Recu...
01 Knapsack Memoization: • 01 Knapsack using Memo...
01 Knapsack DP: • 01 Knapsack Tabulation...
#dp #subsetsum #01knapsack

[@aayushijain6606]

Don't waste your time in watching this video. Just focusing on the odd and even sum concept in most part of this video instead of explaining the concept for this question.

[@akankshasharma148]

Great explanation!!

[@techdose4u]

Thanks

[@aniketsriwastva6345]

Great explaination sir

[@techdose4u]

Thanks

[@sridharanshooriya772]

Wow! explained it clear as a crystal! Thank you very much surya!

[@techdose4u]

Welcome :)

[@yubhav]

For all those who did not understand why he did not initialize 0th column elements to true, so he basically tried to include that using ( nums[ i-1 ] == j ) condition which anyways means the same. Even though the explanation was great, but in my opinion it is not a good practice to write the code like this, as the code is not understandable for the one who is seeing that the first time and it is not right to put up conditions in that manner (atleast that's what I think) even if it means the same. Instead it would be better for you to separately initialize your base case like this. This way you can relate to subset sum even more. for(int j = 0; j

[@guptaayush75]

Why will u make the whole first column true?

[@anushacheedella2291]

Crystal clear explanation 👌

[@techdose4u]

Thanks :)

[@chekweitan]

I couldn't comprehend those top-voted answer in the leetcode discussion. But your approach I understood, thanks.

[@priyadarshanr296]

I'm following u for quite a long time, u r doing a great work ,keep doing what u r doing

[@techdose4u]

Thanks

[@UEC_UdayanBiswas]

bhaiya, you don't know how much you helped me to unederstand dynamic programming, i searched so many vedioes but at last found yours channel. Can't describe but thank you❤️.

[@AtulDislay]

Keep making these videos. really helpful 👍

[@techdose4u]

Sure

[@rohitshirur7640]

Just Similar to Subset Sum Problem Python code No need to pass 0 or n-1 as a parameter easy to track the process tree Hope it helps :) def canPartition(arr): n = len(arr) if sum(arr) % 2 != 0: return False comp_sum = sum(arr) // 2 def Bottom_up(n, arr, comp_sum, dp): for i in range(1, n+1): for j in range(1, comp_sum+1): if j < arr[i-1]: dp[i][j] = dp[i-1][j] else: dp[i][j] = max(dp[i-1][j], dp[i-1][j-arr[i-1]]) col = comp_sum row = n dp = [[0 for i in range(col+1)] for j in range(row+1)] dp[0][0] = 1 for i in range(1, row+1): dp[i][0] = 0 for i in range(1, col+1): dp[0][i] = 0 Bottom_up(n, arr, comp_sum, dp) return dp[row][col]

[@anoops7974]

Thank you so much. You are doing a great job. This video helped me a lot

[@techdose4u]

Welcome :)

[@ADITYASINGH-og9ml]

Can you give a pdf of all the important questions of all topics such that it is the most important from your point of view as important for placement. This will really help for us as there are so many questions we can not do all question.

[@ytg6663]

R u placed

[@mwshubham]

One of mine worst nightmare about dp is finally gone with your dp playlist. Thank you

[@techdose4u]

Welcome :)

[@madhav3444]

One doubt, In this code you filled all the first row(i=0) and first column(j=0) to false, but in sub set problem you filled only the first row(i=0) to false because sum(>=1) can not be formed with taking zero elements, and first column(j=0) to true becuase sum = 0 can be form without taking any elements. So why this change ? Thank you

[@anandravindran5160]

The question mentions that you will be provided with an array that contains only positive integers. This means that the sum of the array will never be 0, which implies that sum/2 will also never be 0. You also need a minimum of 2 elements in the array in order to be able to split it. Therefore, all the values in i = 0 ( i.e., number of elements) row will be false, and all the values in j = 0 (i.e., sum = 0) column will also be false.

[@RG-yj4cb]

@@anandravindran5160 thanks for the comment, I was also getting confused there. And, @TechDose has not mentioned this subtlety in the video leaving viewers not grasping all aspects of the problem.

[@RG-yj4cb]

Also, peeps note that Subset Sum Code will also work too!

[@RG-yj4cb]

DP table with SubsetSum code applied on current que: 1 0 0 0 0 0 1 1 0 0 0 0 1 1 1 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 DP table with recommended code of TechDose: 0 0 0 0 0 0 0 1 0 0 0 0 0 1 1 1 0 0 0 1 1 1 1 1 0 1 1 1 1 1

[@rohandevaki4349]

at 11:21 . memo is storing the integer values at first? how are you comparing it with -1? at line 10? you are storing the boolean value from the subset sum subproblems, but you are comparing with -1? we cant return a integer value to a boolean type function, what are you doing? even in line 13, its the same conversion of data type issue

[@MrRahulsangwan]

your all videos are great brother

[@techdose4u]

Thanks

[@Rasheed21]

For this one, if you don't pay attention to the word "partition" , you could be easily misled to think any two sets are fine even if there are still elements remaining. So keep in mind that all elements must be included in one set or the other. It's also not intuitive that this implies half the sum of the all elements is the target value and the natural instinct would be to leave that unknown only verifying when all the elements have been consumed. This wouldn't then be Knapsack.

[@thesujaii]

Is it necessary condition that the the given array should be a union of subsets with equal sum?????

[@tanmaydhawale3532]

intuition op 🔥🔥

[@techdose4u]

👍🏼

[@bestsaurabh]

What is the problem is slightly modified? Can the array be partitioned into 2 parts of equal sum, 1. Given we can leave some of the elements in the array. 2. Element can be part of only one subset and a single occurrence of each element obviously? Can you please share your thoughts on this?

[@techdose4u]

Then this problem will get modified to find the number of times a sum X can occur from subsets of a given set. If sum X occurs more than 1 time then return True. I will also show this variation in upcoming video.

[@shuchitam3868]

we can use 1 -d array to optimize the space. When i am trying the logic in 1-D array i am getting worng answer for [1,2,5].. Can you tell me what's wrong in my logic? boolean partition[]= new boolean[sum+1]; partition[0]=true; for(int num:nums){ for(int s=0;s

[@AmitKumar-fz3ec]

Thanks , its helping me build my intuition towards handling these kinds of questions.

[@souparnadutta7770]

Great explanation,sir. I have a doubt. Sir aren't we taking dp[0][0]=false in the c++ code for dp table whereas it should be true?

[@MGtvMusic]

The reason for that is,We cannot have the required sum zero and obtain that by any number of elements,Because that would be an empty set (not taking those elements),So we need to atleast be able to choose one element to obtain a proper subset,So,The modification from the subset sum problem would be this because not choosing something does not work here!

[@dipeshsaili4468]

is there any need to mem.clear() ? anything it will do with complexity?

[@renon3359]

After watching the last video of subset-sum, I was able to solve this myself. Thank you so much man, your videos are great.

[@techdose4u]

Welcome :)

[@sandeepnallala48]

sir in bottom up approach does that base case wrk sir ? because we should fill the table as T F F F F F ..... T T T T as we did in SS problem.... bcz when i==0, there are no elements therefore we can make only sum 0, so that frst row is T F F F F ..... and if sum is 0, we can frm it anyways therefore first col is T T T. ..... how will btm up code in yours case give crct ans sir?? please correct me if am wrng sir.

[@simrankak7045]

hii i have a doubt isnt for the target 0 we should have i values true?

[@SonuSharma-fc9hd]

Sir can you give the name of your software which you are using ..?? i like your software of teaching

[@adityaojha2701]

Sir can we print two subsets that form the solution using DP approach??

[@praveenjoshi2064]

With the subset sum problem.. we are just preparing S1 with items with sum equals to sum/2.. and pushing other items to S2 (assuming). But what if items in S2 are not forming sum/2. We are not checking If both sets forming sum/2

[@muskankushwah2639]

We can replac if(nums[i-1]==j) dp[i][j]=true; Condition by simply assigning dp[0][0]=true in starting.

[@Sky-nt1hy]

Hi ! I have one question. Doesn't it have to be if(j==0) dp[i][j]=true? in line 48? Array is initialized with false so can would this code satisfy the base conditions (j==0 -> dp[i][j]=true)? Thank you!

[@madhav3444]

Yes same doubt, do you know the reason? Thank you

[@aravinth.s]

Yes ,same doubt

[@JJ-qv8co]

Dear chingling,aravind,manav, It is the same logic as before, the difference is that here for the case where nums[i-1] == j , it directly assigns true but earlier it used to check in the table[i-1][0] column to get True. So both are correct ways to write the subset sum code. Hope this helps, Max Andrew Goliath II, CTO, Dynamax Technologies, California, USA

[@glenfernandes253]

yes, I think its wrong. I think this has to be the case for base cases: for i in range(n+1): for j in range(w+1): if i == 0 and j == 0: dp[i][j] = True elif j == 0: dp[i][j] = True elif i == 0: dp[i][j] = False

[@amitpatwal09]

is the base condition in the code correct for j==0 ? which is different from sub set problem. because of which we need to add 3rd additional check, we can set T for j=0.

[@forgotten_menace]

what if no. of subsets is 3 what should we change?

[@techdose4u]

DP + BitMasking

[@Jay-vc8jd]

can we use Prefix indexing in solving this problem??

[@arpandas5974]

can we track the subsets????

[@psettii]

In the memo approach ,mem is a int type and subsetSum function returns a boolean type .if(mem[pos][sum]!=-1) return mem[pos][sum]; Is this ok ?

[@techdose4u]

Yea. As long as values are 0 and 1.

[@MGtvMusic]

Would work for C/C++ ,Wouldn't work for Java

[@shraddhapatil8255]

Pls tell me what is spacce complexity

[@adithyanarayan9976]

It however fails this particular hidden test case: N = 3 arr[ ] ={ 856, 404, 278}; wherein although the sum of the elements results in an even number (1538), none of the combinations whilst being put in either subset totals up to 769 (sum/2). Would appreciate it if you could clear this out for me as I've been stuck at this for quite sometime now.

[@dhanashreegodase4445]

can u plz make video for Partition to K Equal Sum Subsets?

[@yashwanthyash2665]

sir,can you solve subset of A=(1,2,3)

[@tushardhote6393]

How can we do it with 1D boolean array. I have a doubt in 1D array approach. please explain that approach in further videos.. Thank you.

[@priyank907]

Tech dose is op

[@Phoenix-xi2gy]

Sir, I have a Problem request - Kth Largest sum contiguous subarray. I was able to solve it using heap. But i am not able to understand its optimised solution.. I would be really grateful if u helped

[@anasarahmad3198]

Do it with Sliding Window method. The time complexity will be O(n). Hope that helps😃

[@MrSteamLp]

ehrenmann

[@syedkaja2045]

cant understand how this statement works num[pos][sum]=subset(nums,n,pos+1,sum-num[pos]) || subset(nums,n,pos+1,sum) i have never came across statement like this can anyone please help!! using the or operator

[@techdose4u]

Or will return true if there exists atleast one possible path (by including or excluding the present item). So we need to take OR.

[@syedkaja2045]

@@techdose4u oh ok thanks sir

[@syedkaja2045]

pls upload videos daily

[@syedkaja2045]

pls upload videos daily

[@monildand4366]

Can you make video on, find median in a matrix of R*C dimensions where all rows are sorted and R*C is odd.

[@yitingg7942]

I did exactly the same but TLE!!!! 的😭😭😭😭

[@techdose4u]

Ohoo....Apart from doing problems, do read your messages too 😂

[@yitingg7942]

@@techdose4u Messages ?

[@techdose4u]

@YTFish G Check your📱😆

[@anandkrishnan72]

This solution isnt even accepted by leetcode anymore bruh

[@mehershrishtinigam5449]

bruh fr?