Partition equal subset sum | Equal sum partition | Dynamic Programming | Leetcode
ฝัง
- เผยแพร่เมื่อ 5 ก.ย. 2024
- 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
I'm following u for quite a long time, u r doing a great work ,keep doing what u r doing
Thanks
Wow! explained it clear as a crystal! Thank you very much surya!
Welcome :)
One of mine worst nightmare about dp is finally gone with your dp playlist. Thank you
Welcome :)
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.
R u placed
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❤️.
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
Why will u make the whole first column true?
Keep making these videos. really helpful 👍
Sure
I couldn't comprehend those top-voted answer in the leetcode discussion.
But your approach I understood, thanks.
Great explanation!!
Thanks
Great explaination sir
Thanks
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
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.
@@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.
Also, peeps note that Subset Sum Code will also work too!
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
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.
Thanks , its helping me build my intuition towards handling these kinds of questions.
Crystal clear explanation 👌
Thanks :)
After watching the last video of subset-sum, I was able to solve this myself. Thank you so much man, your videos are great.
Welcome :)
Thank you so much. You are doing a great job. This video helped me a lot
Welcome :)
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]
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.
your all videos are great brother
Thanks
We can replac
if(nums[i-1]==j)
dp[i][j]=true;
Condition by simply assigning
dp[0][0]=true
in starting.
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?
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.
intuition op 🔥🔥
👍🏼
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
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?
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!
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
what if no. of subsets is 3 what should we change?
DP + BitMasking
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.
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
can u plz make video for Partition to K Equal Sum Subsets?
Is it necessary condition that the the given array should be a union of subsets with equal sum?????
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 ?
Yea. As long as values are 0 and 1.
Would work for C/C++ ,Wouldn't work for Java
is there any need to mem.clear() ? anything it will do with complexity?
Sir can we print two subsets that form the solution using DP approach??
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.
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.
ehrenmann
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!
Yes same doubt, do you know the reason? Thank you
Yes ,same doubt
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
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
can we use Prefix indexing in solving this problem??
Tech dose is op
Pls tell me what is spacce complexity
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.
hii i have a doubt isnt for the target 0 we should have i values true?
sir,can you solve subset of
A=(1,2,3)
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
Or will return true if there exists atleast one possible path (by including or excluding the present item). So we need to take OR.
@@techdose4u oh ok thanks sir
pls upload videos daily
pls upload videos daily
Sir can you give the name of your software which you are using ..??
i like your software of teaching
can we track the subsets????
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
Do it with Sliding Window method. The time complexity will be O(n). Hope that helps😃
I did exactly the same but TLE!!!! 的😭😭😭😭
Ohoo....Apart from doing problems, do read your messages too 😂
@@techdose4u Messages ?
@YTFish G Check your📱😆
Can you make video on, find median in a matrix of R*C dimensions where all rows are sorted and R*C is odd.
This solution isnt even accepted by leetcode anymore bruh
bruh fr?