Given a set of non negative numbers and a total, find if there exists a subset in this set whose sum is same as total. github.com/mis... github.com/mis...
I think your explanations are not very intuitive. You completely skip the idea of breaking problem in to subproblem and constructing solution from optimal solution of its subproblems. Instead of going through the tedious table construction exercise maybe you should talk more about how to figure out subproblems, the core logic.
The reason he's going back is because you're subtracting j from i. Think of it this way, let's call the matrix T, now notice how every time T[ i, j ] == i he always goes back to the first column and end up being true since the whole column it's true, this is because you up once because you already used the value at i, now you subtract j - i (j being the sum and i being the current value) you will end up with 0, and 0 always equals to true. This makes sense since you will always be able to come up with the sum of a number that has that number itself in the set of values ex (sum = 8, set: 2, 3, 7, 8, 10). Now that's what he's doing everything he goes back i times, he first goes up, subtracting the value already used, then he goes back i times to see if the remainder from the subtraction has a sum from the remaining values that are left. Ex. (sum = 11, set: 2, 3, 7, 8, 10) lets say we on i = 8, row 8, we do subtraction: (sum = 3, set: 2, 3, 7, 10) since we used 8 already we take it off the list (going up one) and then sum is now 3 since we subtracted 8 from 11 (you go back 8 times) and this will return true since theres a 3 in the set of values and the sum itself is three. I hopes this helps.
For easier backtracking i'd add one more row in the beginning (element 0), that pretty much guarantees you always end up in the upper left corner without worrying about index out of bound issues and checks.
Note: When I ran the logic presented at the end of this video in java. I got an arrayindexoutofbounds exception. The problem here is that j < input [j] should be changed to j < input[j-1]
There was direct solution provided for the tabulation solution but I couldn't able to grasp how actually it's working. Now everything is clear to me after your explanation. Thanks a lot.
This approach is great but has a high space complexity (O(w*n) where w is the number of bits you use to represent the required sum and n is the number of items in the list). I tried using a adjacency list instead where the key is the value of the required sum at every step (basically the columns in this matrix) and the value is the list of items which satisfy the sum. I think that it has a lower space complexity. Also, algorithms like these usually have pseudo-polynomial time complexity. Meaning, that the overall time complexity depends on how you represent the total sum required. For example, if the required sum is 100, we are gonna have 0-100 indexes in columns or keys (in my approach). Anyway, thanks for taking your time out and explaining this stuff Tooshar :D
Sir If you start by explaining the recursive solution to any problem, then it would be quite easy for beginners to understand the concept of DP more effectively . Some questions that were left unanswered in the videos like, why are we copying the value from the above cell or why are we moving T[i] steps back can be best explained by the recursive solution.
I am making a minesweeper solver, so I made an algorithm for subsetSum. However, I needed every possible subset, not just whether there existed one, and also needed to have multiple instances of the same value in the set. What I did was I started at the first value in the set, added any solutions to my solutionset, then I added the next number, and added solutions where the rightmost value was present. I saved some time by calculating max/min sum of the set so I can immediately rule out values if they are too high/low. I'm not sure how better this algorithm is that brute force, however.
Thanks Tushar, great exercise and lesson. i believe that if we would like to modify the problem so repetitions are allowed the basic condition should be modified as follows: if (j < input[i]) T[i][j] = T[i-1][j] else T[i][j] = T[i-1][j] || T[i][j-input[i]]
If this code doesn't works you then, you should know that the first row should be initialized all False (the row which is even above the (0, 0) here because we need to look upwards each iteration so there should be something to look for in first iteration.
Some comments are saying this is unhelpful, but I found this exactly what I needed. But I already understood it conceptually and just needed help figuring out the algorithm, other people might need something different.
Guys He is taking out some time from his busy schedule to teach us,. He is trying his best to explain us. Please show some respect and let's not discourage him from uploading other wonderful tutorials.
thank you sir. i am struggling in dynamic programming . after watching your video , i finally easily understand the concept that how the dynamic programming works
Extremely easy way to make things understandable...I had seen your video about 0/1 Knapsack and the concept is exactly the same that is been applied here...your effort is highly appreciated and my suggestion to others, try watching 0/1 Knapsack video first and then come back. You might be able to relate and understand it well. Thank you :)
It's similar to Knapsack problem. Actually the memo matrix can be optimized to one dimensional array. Hoping the author can add the optimization content in future videos.
Hi Tushar, Thank you for your video. Some thoughts: 1.You don't need (in code) the matrix - one row is quite enough 2.Since all info is copied from above the values in current row can be obtained from this same current row 3.Instead of denoting the corresponding cells with T(rue) it's much better and reasonable to do this with numerous of corresponding term-value. For example, the matrix of the video would be: [0, f, 2, f, f, f, f, f, f, f, f, f] [0, f, 2, 3, f, 3, f, f, f, f, f, f] [0, f, 2, 3, f, 3, f, 7, f, 7, 7, f] [0, f, 2, 3, f, 3, f, 7, 8, 7, 7, 8] [0, f, 2, 3, f, 3, f, 7, 8, 7, 7, 8] 4.You don't need to do calculations to all the cells - you only need add the value of current row to the values of columns (copied from the above non-negative values) For example: to get the second row from the first one we need only 2 operations: to add 0+3 -> we get 3 in the column 3=0+3 to add 2+3 -> we get 3 in the column 5=2+3 to get the third row from the second one we need only 3 operations: to add 0+7 -> we get 7 in the column 7=0+7 to add 2+7 -> we get 7 in the column 9=2+7 to add 3+7 -> we get 7 in the column 10=3+7 to add 5+7 -> we get 7 in the column 12=5+7>11 - in fact we don't need this operation 5.So to get the result we check the column 11. Since there we have the value 8 - we go to the left by 8 and obtain 3, then go to the left by 3 and obtain 0. So 11=8+3 Here is the code in python: # def subset_with_given_sum(li,m): a=[0] b=[0]+[-1]*m for x in li: c=[] for i in a: if i+x0: result.append(b[j]) j-=b[j] print('{} -> {}'.format(result,m)) return result print('no such sum -> {}'.format(m)) return def test(): li=[2,3,7,8,10] m=11 subset_with_given_sum(li,m) m=14 subset_with_given_sum(li,m) m=16 subset_with_given_sum(li,m) m=19 subset_with_given_sum(li,m)
similar to Subset Sum Problemwhich asks us to find if there is a subset whose sum equals to target value. For this problem, the target value is exactly the half of sum of array. Following are the two main steps to solve this problem: 1) Calculate sum of the array. If sum is odd, there can not be two subsets with equal sum, so return false. 2) If sum of array elements is even, calculate sum/2 and find a subset of array(video method) with sum equal to sum/2.
There can be multiple subsets for a particular sum. For example if S={1,2,3} and sum = 3 then possible subsets are {1,2} and {3}. How can we print all of them? Your approach of tracing back will only give a single subset I guess. Other than that, great video and nicely explained :)
If we look at equations at last, that suggest there is 0th row(didn't show up here in video) filled with false, like 0th column is filled with true value.
Could have also incorporated the logic of including and excluding number explicitly rather than if the element on the upper column is True or not. But thanks for the explanation anyways, it greatly helped.
Interesting fact, if you take the set of numbers corresponding to a state in US, and take sum to be 269, you can calculate number of ties in the US election!
Hi Tushar, Your videos are very helpful in understanding the "working" of the algorithm. If you could explain why the recurrence relation was formed or why a 2D matrix with j 1...sum was used, I would love that. While trying to solve on my own, I used a 1D matrix and couldn't find the solution. After seeing the 2D matrix and recurrence relation, I could solve it. So learning how to intuitively decide on the strategy will be extremely helpful for me.
I might have a small explanation to your question based on my little knowledge. I have observed the 2D approach being taken when there is something finite , like the no. of elements here can be used only once, Even in the case of the LCS problem , the string is finite .. in case of knapsack , the items are finite.
Try to solve it with recursion first and then look for the parameters that are changing when you are calling recursion for smaller sub problems... for example in recursion solution for this problem size of the array and value of k both are changing hence it’s 2D dp .. finding a recursion solution and coming up to this conclusion is much more intuitive ..
Isn’t it better to sort O(nlogn) then use the sliding pointers technique? Two pointers each pointing at one end of the array, move pointers according to sum being greater or less than the desired sum.
Tushar, thanks for another great video! I have a question: do the numbers have to be in ascending order? And does it work when you have duplicated numbers. Thanks again.
+Tushar Roy Thanks for the quick reply! My last question: if i found that a T[i][total] is TRUE, even if the algorithm isn't finished, can I return true already?
if I have 6,4,3,2 and 1 in the array, then won't [6,5], [5,4,2], [5,3,2,1] also be subsets, if we backtrack like that, I don't think we can get proper solutions.
Nice explanation. Regarding the algo, I don't like the idea of allocating array of the size of sum. Assume 2 numbers, 4mn and 6mn and sum of 10mn, array of size 10mn will cause issues. Is there a different data structure which can be used here ?
You should explain why we need to do this instead of how we need to do this. The way you explained DP in this video, it will only force the viewers to memorize the procedure which is not the best way to learn algorithms.
i didn't get the essence of dp.. if this problem came up on interview, idk how would i have solved right then. i mean how to come up with the solution.. that's the main issue, mere solution is not enough
At 4:31, do we have to go one row above and move 7 steps back to check if the value is true or not, whats the problem of checking it on the same row? As the values from the above row will be copied to the subsequent rows if the element is larger. for example for 3rd row, all the values from 2nd row from column 1 to column 6 are copied.
Turn on closed captions and see what youtube translates Tushar's name into at 0:02
:)
that's funny :P
for people don't want to go back to 0:02. "Hello friends my name is too short"
that's messed up :)
funny things..haha
The way you tediously run through the grunt work of the algorithms is really effective for me. Thank you for doing this for free.
New name for the channel: "Yes, we'll use Dynamic Programming"
I think your explanations are not very intuitive. You completely skip the idea of breaking problem in to subproblem and constructing solution from optimal solution of its subproblems. Instead of going through the tedious table construction exercise maybe you should talk more about how to figure out subproblems, the core logic.
Thanks for taking it constructively. Keep up the good work!
true. talk more about the concept and the logic.
Agree, why you move back no of steps, why you take it from top. focus on the core logic
The reason he's going back is because you're subtracting j from i. Think of it this way, let's call the matrix T, now notice how every time T[ i, j ] == i he always goes back to the first column and end up being true since the whole column it's true, this is because you up once because you already used the value at i, now you subtract j - i (j being the sum and i being the current value) you will end up with 0, and 0 always equals to true. This makes sense since you will always be able to come up with the sum of a number that has that number itself in the set of values ex (sum = 8, set: 2, 3, 7, 8, 10).
Now that's what he's doing everything he goes back i times, he first goes up, subtracting the value already used, then he goes back i times to see if the remainder from the subtraction has a sum from the remaining values that are left. Ex. (sum = 11, set: 2, 3, 7, 8, 10) lets say we on i = 8, row 8, we do subtraction: (sum = 3, set: 2, 3, 7, 10) since we used 8 already we take it off the list (going up one) and then sum is now 3 since we subtracted 8 from 11 (you go back 8 times) and this will return true since theres a 3 in the set of values and the sum itself is three. I hopes this helps.
Doesn't this algo assume the array to be sorted?
"How do you solve this problem? Yes, we'll use Dynamic Programming."
😂😂
For easier backtracking i'd add one more row in the beginning (element 0), that pretty much guarantees you always end up in the upper left corner without worrying about index out of bound issues and checks.
Note: When I ran the logic presented at the end of this video in java. I got an arrayindexoutofbounds exception. The problem here is that j < input [j] should be changed to j < input[j-1]
Thanks alot, this really helped me. By you showing how to calculate the values T[i][j] I could finally understand what the idea was.
There was direct solution provided for the tabulation solution but I couldn't able to grasp how actually it's working.
Now everything is clear to me after your explanation. Thanks a lot.
This approach is great but has a high space complexity (O(w*n) where w is the number of bits you use to represent the required sum and n is the number of items in the list). I tried using a adjacency list instead where the key is the value of the required sum at every step (basically the columns in this matrix) and the value is the list of items which satisfy the sum. I think that it has a lower space complexity. Also, algorithms like these usually have pseudo-polynomial time complexity. Meaning, that the overall time complexity depends on how you represent the total sum required. For example, if the required sum is 100, we are gonna have 0-100 indexes in columns or keys (in my approach). Anyway, thanks for taking your time out and explaining this stuff Tooshar :D
Sir
If you start by explaining the recursive solution to any problem, then it would be quite easy for beginners to understand the concept of DP more effectively . Some questions that were left unanswered in the videos like, why are we copying the value from the above cell or why are we moving T[i] steps back can be best explained by the recursive solution.
congo u got job in Microsoft
@@cool_guy_Vaibhav 🤣🤣🤣🤣
@@ultimatecreed5144 Bro she really got job in Microsoft
@@ultimatecreed5144 he is apeaking truth bro
You explained how this algorithm works, not why this algorithm works. You taught how to do the problem, not how to build logic for such problems.
Yeah he just told how to fill the table and nothing else
Bruh watch Abdul Bari. He is the legend of algorithms.
Wow, this made my life much easier. Thank you! I was noticing the pattern in the 2d matrix, but was not understanding why this pattern made sense.
You're the only one that understands what you're talking about. You start filling up a table base on an algorithm you didn't explain
If you are a software engineer...
you are awesome
That's why you started your own channel :P All the best..
@@thanga2317 hahahahaha
Directly jumping on the board without telling anything how to approach😂😂😂
thank you!!! great tabulation explanation. so easy to understand the code with this video
Thanks for jumping straight into useful explanation instead of spending 10 min talking about obvious stuff like many videos
I am making a minesweeper solver, so I made an algorithm for subsetSum. However, I needed every possible subset, not just whether there existed one, and also needed to have multiple instances of the same value in the set. What I did was I started at the first value in the set, added any solutions to my solutionset, then I added the next number, and added solutions where the rightmost value was present. I saved some time by calculating max/min sum of the set so I can immediately rule out values if they are too high/low. I'm not sure how better this algorithm is that brute force, however.
Thanks man! U helped me a lot... Please keep making such useful videos for us
Thanks a lot Tushar, I didn't know until now how to solve subset sum problem with dp, but now I get it !
Thanks man....despite being so busy you took out time to help people like us for free....Highly appreciated!
Always love your videos, Tushar. They are To The Point ! Drive home the point quickly.. Thanks !
Thanks Tushar, great exercise and lesson.
i believe that if we would like to modify the problem so repetitions are allowed the basic condition should be modified as follows:
if (j < input[i])
T[i][j] = T[i-1][j]
else
T[i][j] = T[i-1][j] || T[i][j-input[i]]
If elements repeat, then it's not a set :)
Best explanation without water
If this code doesn't works you then, you should know that the first row should be initialized all False (the row which is even above the (0, 0) here because we need to look upwards each iteration so there should be something to look for in first iteration.
I really appreciate this. Been trying to figure this out lately, and you explained it very well
So, it is very similar to 0/1 knapsack. instead of values, we need to check for True/False
Thank you u are live savour
Keep going god bless u
Some comments are saying this is unhelpful, but I found this exactly what I needed. But I already understood it conceptually and just needed help figuring out the algorithm, other people might need something different.
Your videos are so good. it helped me a lot, thank you so much sharing your experience and knowledge
If you are a programmer this explanation should be enough for you. If you don't like it, search for another solution which helps you more.
Guys He is taking out some time from his busy schedule to teach us,. He is trying his best to explain us. Please show some respect and let's not discourage him from uploading other wonderful tutorials.
and he should'nt
Yup. He works for Apple.
If it was up to me, I would leave in the middle of the interview. This is not how you approach a question.
can u help me with the code , to traverse the matrix and find the relevant elements that add to the specified sum
well said
This solution requires the array to be sorted which is not typically specified in the problem.
thank you sir. i am struggling in dynamic programming . after watching your video , i finally easily understand the concept that how the dynamic programming works
Extremely easy way to make things understandable...I had seen your video about 0/1 Knapsack and the concept is exactly the same that is been applied here...your effort is highly appreciated and my suggestion to others, try watching 0/1 Knapsack video first and then come back. You might be able to relate and understand it well. Thank you :)
It's similar to Knapsack problem. Actually the memo matrix can be optimized to one dimensional array. Hoping the author can add the optimization content in future videos.
The intuition behind dynamic programming is a recursive definition
f(i, sum) = f(i+1, sum) OR f(i+i, sum-arr[i])
Hi Tushar,
Thank you for your video.
Some thoughts:
1.You don't need (in code) the matrix - one row is quite enough
2.Since all info is copied from above the values in current row can be obtained from this same current row
3.Instead of denoting the corresponding cells with T(rue) it's much better and reasonable to do this with numerous of corresponding term-value.
For example, the matrix of the video would be:
[0, f, 2, f, f, f, f, f, f, f, f, f]
[0, f, 2, 3, f, 3, f, f, f, f, f, f]
[0, f, 2, 3, f, 3, f, 7, f, 7, 7, f]
[0, f, 2, 3, f, 3, f, 7, 8, 7, 7, 8]
[0, f, 2, 3, f, 3, f, 7, 8, 7, 7, 8]
4.You don't need to do calculations to all the cells - you only need add the value of current row to the values of columns (copied from the above non-negative values)
For example:
to get the second row from the first one we need only 2 operations:
to add 0+3 -> we get 3 in the column 3=0+3
to add 2+3 -> we get 3 in the column 5=2+3
to get the third row from the second one we need only 3 operations:
to add 0+7 -> we get 7 in the column 7=0+7
to add 2+7 -> we get 7 in the column 9=2+7
to add 3+7 -> we get 7 in the column 10=3+7
to add 5+7 -> we get 7 in the column 12=5+7>11 - in fact we don't need this operation
5.So to get the result we check the column 11.
Since there we have the value 8 - we go to the left by 8 and obtain 3, then go to the left by 3 and obtain 0.
So 11=8+3
Here is the code in python:
#
def subset_with_given_sum(li,m):
a=[0]
b=[0]+[-1]*m
for x in li:
c=[]
for i in a:
if i+x0:
result.append(b[j])
j-=b[j]
print('{} -> {}'.format(result,m))
return result
print('no such sum -> {}'.format(m))
return
def test():
li=[2,3,7,8,10]
m=11
subset_with_given_sum(li,m)
m=14
subset_with_given_sum(li,m)
m=16
subset_with_given_sum(li,m)
m=19
subset_with_given_sum(li,m)
Thanks buddy, it cleared up the concept for me.
Good explanation, Tushar.
exactly what I was looking for
All your videos are really amazing! Thanks a lot! :)
Thanks a lot !Didn't find anything like this on yt
I love u man. I passed this subject because of ur explanations
Very nice explanation sir. Your tutorial is very helpful
These videos are better then most of the other channels, but i still wish you could explain the problems in an intuitive way...
Good illustration
similar to Subset Sum Problemwhich asks us to find if there
is a subset whose sum equals to target value. For this problem, the
target value is exactly the half of sum of array.
Following are the two main steps to solve this problem:
1) Calculate sum of the array. If sum is odd, there can not be two subsets with equal sum, so return false.
2) If sum of array elements is even, calculate sum/2 and find a subset of array(video method) with sum equal to sum/2.
From Korea, with infinite love....
Thanks for explaning; the algorithm is fun!
There can be multiple subsets for a particular sum. For example if S={1,2,3} and sum = 3 then possible subsets are {1,2} and {3}. How can we print all of them? Your approach of tracing back will only give a single subset I guess. Other than that, great video and nicely explained :)
I think it would produce the same output if we just subtract from current to find the index of cell instead of going r-1 (or row above)
Now I am starting to get it!
If we look at equations at last, that suggest there is 0th row(didn't show up here in video) filled with false, like 0th column is filled with true value.
Thanks a lot! Saved my day!
old but it's gold
Explaining recursive equations in Dp is major task
Thank you so much for this . Tutorial.
Amazing clarity on ur presentations, really helpful, thnx!
that's literally super intelligent as a solution
Good job, Thanks for the effort!
what if there are more subsets fulfilling sum value... how to trace
You would need to do an exhaustive search. It’s extremely inefficient
Awesome. Also, if all the interviewer wants is a true-false answer, we can just use an array instead of a matrix.
Thanks a lot.. awesome explanation!
Thanks for explaining so well !!!.
Thanks, it helped me to understand the solution
Thanks great explanation
nice video gautam gambhir
Great explanation..thanks!
will go three steps back, what a logic!
Hi Tushar, Could you please tell me how to print all the available subsets for a given number K.
very good, thanks
Could have also incorporated the logic of including and excluding number explicitly rather than if the element on the upper column is True or not. But thanks for the explanation anyways, it greatly helped.
Interesting fact, if you take the set of numbers corresponding to a state in US, and take sum to be 269, you can calculate number of ties in the US election!
Beautiful explanation sir..👍✌ wondering since days how this algo works.😊 thanks a lot sir.
Is there any way we can also display the subset?
Legend🔥
Hi Tushar,
Your videos are very helpful in understanding the "working" of the algorithm. If you could explain why the recurrence relation was formed or why a 2D matrix with j 1...sum was used, I would love that. While trying to solve on my own, I used a 1D matrix and couldn't find the solution. After seeing the 2D matrix and recurrence relation, I could solve it. So learning how to intuitively decide on the strategy will be extremely helpful for me.
I might have a small explanation to your question based on my little knowledge.
I have observed the 2D approach being taken when there is something finite , like the no. of elements here
can be used only once, Even in the case of the LCS problem , the string is finite .. in case of knapsack , the items are finite.
Try to solve it with recursion first and then look for the parameters that are changing when you are calling recursion for smaller sub problems... for example in recursion solution for this problem size of the array and value of k both are changing hence it’s 2D dp .. finding a recursion solution and coming up to this conclusion is much more intuitive ..
Isn’t it better to sort O(nlogn) then use the sliding pointers technique? Two pointers each pointing at one end of the array, move pointers according to sum being greater or less than the desired sum.
dp always op. dp sabka baap hai
Thank u for your helpful video!
What is the input size for our example 11 + 5?
Thanks alot for all videos 😚
Thank you so much from Bangladesh
Tushar, thanks for another great video! I have a question: do the numbers have to be in ascending order? And does it work when you have duplicated numbers. Thanks again.
+Tushar Roy Thanks for the quick reply! My last question: if i found that a T[i][total] is TRUE, even if the algorithm isn't finished, can I return true already?
+Tushar Roy Thank you very much, you've been really helpful. Keep up with these great videos.
This is not easy to follow. We should be understanding WHY we need to fill out the table in that way. That isn't really explained here.
if I have 6,4,3,2 and 1 in the array, then won't [6,5], [5,4,2], [5,3,2,1] also be subsets, if we backtrack like that, I don't think we can get proper solutions.
Great explaination .
am I the only one who thinks this problem is similar to total unique ways to exchange coin with a given amount
It is same as "coin change problem" in dynamic programming
I think top-down technique would be more easier to understand..
but this was a good video thanks :)
Nice explanation. Regarding the algo, I don't like the idea of allocating array of the size of sum. Assume 2 numbers, 4mn and 6mn and sum of 10mn, array of size 10mn will cause issues. Is there a different data structure which can be used here ?
You just memorized the solution bro.
Hi Tushar, thanks for the video. I was wondering, is there any way to tell the number of possible subsets that make up the sum from this table?
can anyone share the code where we print the subsets too along with true or false in this same code shared by Tushar sir?
Brilliant method!
How to identify whether there are multiple subsets which can produce the given sum? Also, how to find the elements constituting each subset?
that's a classic knapsack problem try to find it, it will be pretty usefull
You should explain why we need to do this instead of how we need to do this.
The way you explained DP in this video, it will only force the viewers to memorize the procedure which is not the best way to learn algorithms.
i didn't get the essence of dp.. if this problem came up on interview, idk how would i have solved right then. i mean how to come up with the solution.. that's the main issue, mere solution is not enough
At 4:31, do we have to go one row above and move 7 steps back to check if the value is true or not, whats the problem of checking it on the same row? As the values from the above row will be copied to the subsequent rows if the element is larger. for example for 3rd row, all the values from 2nd row from column 1 to column 6 are copied.