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.
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.
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.
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.
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.
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
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
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.
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.
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]]
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.
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 :)
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 :)
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.
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.
Also, last row is all posible sums that can be generated with weights using once. In this example 2,3,7,8, 10 table is created only till 11, but if you fill it till maximum weight that is 2 + 3 + 7 + 8 + 10 = 30, the last row of T and F shows all posible sums that can be generated using once of [2,3,7,8,10]. Maybe someone that info will be usefull :)
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!
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 ?
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 ..
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.
if 0th row is introduced, it makes a lot more sense. 0th row means that, is it possible to fill with 0 unit money. It is F all the way. after that, fill in 1st row.
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.
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.
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.
Hi Tushar , Can you please tell me how did you traverse from last result node to get the result 3,8 . I did not get how did you jump from last node to above .
seems input array must be in sorted order. Also does this work if the numbers are big. like sum is in millions and input array of size 4 contains in bigger numbers, how big will be the matrix with columns. do we need to follow different approach in this case?
What about the case when there are two or more than two sets of solutions possible? like for set {1,2,3,7,8} and sum 10 we have solutions as {2,8}, {3,7} and {1,2,7}.
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
how it comes that when you reach 7 you take the above Value =T, which mean that the subset you reached until 7 is equal to 2, I don't get it, it seems that contradict logic
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"
"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.
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?
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.
Directly jumping on the board without telling anything how to approach😂😂😂
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.
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
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.
Thanks man! U helped me a lot... Please keep making such useful videos for us
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.
If you are a software engineer...
you are awesome
That's why you started your own channel :P All the best..
@@thanga2317 hahahahaha
Thanks a lot Tushar, I didn't know until now how to solve subset sum problem with dp, but now I get it !
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
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.
Thanks for jumping straight into useful explanation instead of spending 10 min talking about obvious stuff like many videos
I really appreciate this. Been trying to figure this out lately, and you explained it very well
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
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 !
Your videos are so good. it helped me a lot, thank you so much sharing your experience and knowledge
thank you!!! great tabulation explanation. so easy to understand the code with this video
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
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.
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.
So, it is very similar to 0/1 knapsack. instead of values, we need to check for True/False
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
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 :)
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.
All your videos are really amazing! Thanks a lot! :)
This solution requires the array to be sorted which is not typically specified in the problem.
I love u man. I passed this subject because of ur explanations
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 :)
Thanks buddy, it cleared up the concept for me.
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 :)
Best explanation without water
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.
Very nice explanation sir. Your tutorial is very helpful
The intuition behind dynamic programming is a recursive definition
f(i, sum) = f(i+1, sum) OR f(i+i, sum-arr[i])
Thank you u are live savour
Keep going god bless u
Good explanation, Tushar.
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.
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.
Good illustration
Explaining recursive equations in Dp is major task
These videos are better then most of the other channels, but i still wish you could explain the problems in an intuitive way...
Awesome. Also, if all the interviewer wants is a true-false answer, we can just use an array instead of a matrix.
Also, last row is all posible sums that can be generated with weights using once. In this example 2,3,7,8, 10 table is created only till 11, but if you fill it till maximum weight that is 2 + 3 + 7 + 8 + 10 = 30, the last row of T and F shows all posible sums that can be generated using once of [2,3,7,8,10]. Maybe someone that info will be usefull :)
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)
Thanks for explaning; the algorithm is fun!
Hi Tushar, Could you please tell me how to print all the available subsets for a given number K.
Amazing clarity on ur presentations, really helpful, thnx!
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!
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 ?
that's literally super intelligent as a solution
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 ..
From Korea, with infinite love....
Thanks, it helped me to understand the solution
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.
Thanks a lot !Didn't find anything like this on yt
exactly what I was looking for
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?
if 0th row is introduced, it makes a lot more sense. 0th row means that, is it possible to fill with 0 unit money. It is F all the way. after that, fill in 1st row.
What is the input size for our example 11 + 5?
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.
what if there are more subsets fulfilling sum value... how to trace
You would need to do an exhaustive search. It’s extremely inefficient
Hey Tushar, can we use backtracking as well , but i guess worst case complexity will be exponential .
Is there any way we can also display the subset?
Good job, Thanks for the effort!
Thanks alot for all videos 😚
Hi Tushar Roy, I looked at the code. Why should we check whether sum is odd or not? What if my total is sum of all elements and it is odd?
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.
This question seems very similar to the 0-1 knapsack problem... is that true ?
Thank you for your explanation.
I didn't understand why you wrote T when my sum is 0 for all the weights. It should be false right? Basically, why all T in first column.
It 's Really amazing. But i have question, If given input have more then 1 subset is there any way to pull those subsets also.
It is same as "coin change problem" in dynamic programming
There should be N+1 Rows with top row being all False Representing 0 elements as other rows representing elements.
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.
please explain the sub problems also.It's not about the table it's about the sub problems
Awesome! So both of the time complexity and space complexity are O(n * target) right? its a really subtle usage of dp!
and if required sum is in millions but the given set is small, why not sum all combinations and check ?
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
Thanks a lot.. awesome explanation!
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
Hi Tushar , Can you please tell me how did you traverse from last result node to get the result 3,8 . I did not get how did you jump from last node to above .
Thanks a lot! Saved my day!
actually if we sort it and have 2 pointers from end and from beginning , we can easily find the solution in 0(n) time without any space.
sorting itself will take O(nlogn) time
seems input array must be in sorted order. Also does this work if the numbers are big. like sum is in millions and input array of size 4 contains in bigger numbers, how big will be the matrix with columns. do we need to follow different approach in this case?
What about the case when there are two or more than two sets of solutions possible?
like for set {1,2,3,7,8} and sum 10 we have solutions as {2,8}, {3,7} and {1,2,7}.
+Tushar, What if we have negative numbers in the array as well?
am I the only one who thinks this problem is similar to total unique ways to exchange coin with a given amount
Why 0 to 11? Shouldn't it be 0 to 15 since the total sum is 30 and 30 / 2 = 15?
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
how it comes that when you reach 7 you take the above Value =T, which mean that the subset you reached until 7 is equal to 2, I don't get it, it seems that contradict logic
Thank you so much for this . Tutorial.
is there any space optimization we can do? what if array size is 10 elements and required sum is 10000 ?
The complexity increases if I take bigger value in sum variable!