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
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)
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.
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❤️.
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.
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.
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.
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
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.
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.
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.
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
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
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!
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.
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!
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
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
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
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?
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]
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
One of mine worst nightmare about dp is finally gone with your dp playlist. Thank you
Welcome :)
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❤️.
I couldn't comprehend those top-voted answer in the leetcode discussion.
But your approach I understood, thanks.
Wow! explained it clear as a crystal! Thank you very much surya!
Welcome :)
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.
I'm following u for quite a long time, u r doing a great work ,keep doing what u r doing
Thanks
Great explanation!!
Thanks
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.
Keep making these videos. really helpful 👍
Sure
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 :)
Great explaination sir
Thanks
Crystal clear explanation 👌
Thanks :)
We can replac
if(nums[i-1]==j)
dp[i][j]=true;
Condition by simply assigning
dp[0][0]=true
in starting.
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
Thanks , its helping me build my intuition towards handling these kinds of questions.
Thank you so much. You are doing a great job. This video helped me a lot
Welcome :)
your all videos are great brother
Thanks
Is it necessary condition that the the given array should be a union of subsets with equal sum?????
can u plz make video for Partition to K Equal Sum Subsets?
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
Sir can we print two subsets that form the solution using DP approach??
is there any need to mem.clear() ? anything it will do with complexity?
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.
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.
can we use Prefix indexing in solving this problem??
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.
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
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
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.
what if no. of subsets is 3 what should we change?
DP + BitMasking
can we track the subsets????
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
intuition op 🔥🔥
👍🏼
hii i have a doubt isnt for the target 0 we should have i values true?
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!
Pls tell me what is spacce complexity
sir,can you solve subset of
A=(1,2,3)
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.
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
Sir can you give the name of your software which you are using ..??
i like your software of teaching
Tech dose is op
Can you make video on, find median in a matrix of R*C dimensions where all rows are sorted and R*C is odd.
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😃
ehrenmann
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
I did exactly the same but TLE!!!! 的😭😭😭😭
Ohoo....Apart from doing problems, do read your messages too 😂
@@techdose4u Messages ?
@YTFish G Check your📱😆
This solution isnt even accepted by leetcode anymore bruh
bruh fr?