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

[@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❤️.

[@priyadarshanr296]

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

[@techdose4u]

Thanks

[@sridharanshooriya772]

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

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

[@chekweitan]

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

[@mwshubham]

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

[@techdose4u]

Welcome :)

[@sujaigupta6119]

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

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

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

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

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

[@anoops7974]

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

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

[@AmitKumar-fz3ec]

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

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

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

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

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

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

[@adityaojha2701]

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

[@AtulDislay]

Keep making these videos. really helpful 👍

[@techdose4u]

Sure

[@simrankak7045]

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

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

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

[@SonuSharma-fc9hd]

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

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

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

[@Jay-vc8jd]

can we use Prefix indexing in solving this problem??

[@dhanashreegodase4445]

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

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

[@akankshasharma148]

Great explanation!!

[@techdose4u]

Thanks

[@forgotten_menace]

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

[@techdose4u]

DP + BitMasking

[@anushacheedella2291]

Crystal clear explanation 👌

[@techdose4u]

Thanks :)

[@arpandas5974]

can we track the subsets????

[@aniketsriwastva6345]

Great explaination sir

[@techdose4u]

Thanks

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

[@shraddhapatil8255]

Pls tell me what is spacce complexity

[@muskankushwah2639]

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

[@MrRahulsangwan]

your all videos are great brother

[@techdose4u]

Thanks

[@yashwanthyash2665]

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

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

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

[@tanmaydhawale3532]

intuition op 🔥🔥

[@techdose4u]

👍🏼

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

[@priyank907]

Tech dose is op

[@MrSteamLp]

ehrenmann

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