subset sum problem dynamic programming | backtracking sum of subsets
ฝัง
- เผยแพร่เมื่อ 5 ก.ย. 2024
- This is a video lecture which explains subset sum problem solving using both backtracking and dynamic programming methods. This explanation is a little long but once you watch it, you won't ever regret about having watched such a long video. Backtracking takes exponential time to solve the subset sum problem therefore, we solve using it dynamic programming. I am sure you will love the explanation :)
CODE LINK: drive.google.c...
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 :)
explained clearly , leaves no doubt in my mind , thank you sir.
Welcome :)
the best of the explaination i had seen so far
At first I want to thank you.
I was trying to understand how the matrix is fullfilling the XOR logic. When I was trying to dry run the code I found, it was not being match with the logic. I have searched and seen a lot of subset sum problem video, even repeat the knapsack video also. Then suddenly at this time of night I find a channel with less subs and even lesser view. I started with very less expectation but sir forgive me for my previous thoughts. I finally understood what is happening and I found by myself that I have a error in my code. When I am able to find the error, I understood the logic. I feel relaxed.
I will share this channel, and will watch more dp video if u have.
Thanks :)
I really love this video. It explain the problem and gives two solutions. With the first solution it builds the required intuition to understand that the problem show a dynamic programming pattern and use it to build up a bottom-up solution. Thank you very much
Welcome :)
Thank you very much for this explanation, i went over many videos over youtube but didn't get any intuition for this problem, but the way you distinguished both approaches made me understand this problem very well.
Welcome :)
If anyone wants to know how backtracking actually works this is the recommended video. Bro the way you did backtrack till last possibility is amazing. Thank you so much 🙏🏻🥰
Welcome :)
Same feel. I understood backtracking properly with this video. I didn't know that I was doing backtracking when I was coding that method in the first place 😆
most underated channel
😅
bro your explanation is the best! Other videos on youtube don't explain how the table is forming and the sub problems but you explain that.Thanks a lot!
Welcome :)
@@techdose4u bro can you make a video on subset sum divisible by m problem? It's a variant of this problem but harder and i can't understand the approach
This Channel Needs To Be Popular..
Absolutely Great Stuff..
❤❤
Thanks :)
Hi sir, you teach everything very cleanly...please keep teaching us😊
For sure ❤️
Great explanation, i have never seen anyone explain that much in you tube
Thanks
Thanks alot Algo Buddy. Words are not enough to praise you but you are the best teacher, its like a magic that you teach even hardest of hard concept as if it was always easy. You are going to rock algo learning world someday for sure.
Thanks for your motivation bro :)
Gave an applaud to this video and another video of yours. Keep up the good work :)
Thanks for supporting us ❤️
I love this channel, thanks for it, i see i have ameliorated a lot, i will always support it
Thanks 😊
The best explanation!. Made this problem seem so easy . Thanks a lot !
Welcome :)
Superb and clear Explanation..You are very great at making these videos for free...
Thanks
Amazing content. Clearly visible that you are putting a lot of hard work.
Thanks
IF YOU START AN ONLINE COURSE I LL BE THE FIRST ONE TO REGISTER
Thanks bro:)
Thanks a lot for this.❤️. I finally understood it 😭❤️ . Keep up the good work. :')
Welcome 😊
Rona kya isme🙄😂😂
@@ritiksolanki6267 khushi k aansu
God bless you!
I was looking for this type of explanation. Please start some online course on which you will cover these topics in-depth.
Yep. I will do it at some point of time.
one day sir you will become the biggest competitor for many other ppl teaching DSA sir. thanks a lot sir ..... : )
Thanks a lot sir. Now I clearly understood.
Welcome :)
thanks a lot, i understood the concept behind filling this table ,one syggestion it could b better explained using recurssion tree that includes sub problems.
Okay sure
One of the best explanations of subset sum problem!
Hi Tech Dose, the only request I am putting here is, Can you elaborate how the recursive formula came in every dynamic programming videos?
Because after seeing your recursive formula only I am able to understand the logic, If you do consider that also, it would be more helpful. Thanks in advance. And one more, the explanation was awesome!!!
Thanks. I will try to derive the recursive formula from now on.
Thank you brother
👍
This is a good requirement. I have first listened to the explanation, proceeded to write Recursive code first, and then wrote the DP. But in essence from interview point of view, it is better to be able to work with bottom up tabulation approach on the fly rather than going through recursion. Here the detailed explanation for filling the table, makes it intuitive enough to stand on its own.
Next level Explanation ✨
Thanks :)
Literally you are gem Thanks for your quality teaching keep it up
Very nice explanation in "Abob" (above) Video !
:)
Nice explaination but
how can you implement tabulation solution directly from the recursive solution
best way to learn dp is -> 1. find recursive solution, 2. implement memoized version of DP solution from recursive, 3. then at last we can move to tabulation approach
Very well explained! You definitely need more likes..
Thanks for liking ❤️
This is some nice stuff explained superbly!
Thanks
Amazing explanation bro, can't go without liking.
Very well explained 👍 thank you sir..keep making such videos
Welcome :)
clean and crisp
please make a video on time complexity ?how to find it
ur explanations are great
I was looking for such videos. Really helpful 👌👍
Thanks :)
really best lecture perfect!!..
Thanks 😊
Thanks for this magical explanation.
Welcome :)
@TECH DOSE - Nice video , well explained and I cleared doubt on how to track down the nodes but can you please tell me if I want to see what all subset elements are added to get the sum then how to track back from last node that is 3*5 = T
Great video! :) Liked and subscribed!
Thanks 😊
give this man an oscar :)
At first I thought why this is needed because I can iterate all elements in a nested for loop to find the sum. Then I changed {2, 2, 3} and sum {7} instead of 5, by running the attached code. Then it made lot of sense. Instead of needing to iterate with 3 iterator variables over all elements, this method shows a simple technique to get the subset. Now I am convinced. Thanks a lot. Are you converting a n dimensional problem to a 2 dimentional problem with Knapsack?
Very good and clear explanation! Thank you!
Very well explained
Thanks
Would have been great if you explained memoization method before DP method. Good content btw! Thanks!
👍🏼
Appreciate such a clean explanation
Thanks
Really good video. I want to point out something @tech_dose that in your code the order of initializing the array with true and false should be swapped(the first row and first column) since if we initialize the column first it will get overwritten.
understanding recursive intuition is easy, and writing that into dp was tough for me. but now if i can come up with recursive soln, i can easily write that into dp. Thanks to @Tech Dose
Great explanation sir!!
Please also create a video on Sudoku solver🙏
Sure :)
@@techdose4u Thanku🙏
great explanation...
Thank you, sir.
Welcome :)
Great video! The space complexity for dp is O(sum*size(set)) for your method which is bottom-up. But I guess we can perform dp top bottom approach, the Space complexity can be reduced to O(sum+1). Is that correct?
You can just maintain a row to do that
Well illustrated. Thanks
Welcome :)
can you tell me how to print elements of subset
Great job, explaining this! 🎉
crystal clear sir, 🙌🙌👏
Thanks :)
Bro i can't tell i was finding this from last 2 days...... you are an angel 🔥
Please tell me can we initialise the 1st row and column within the nested for loop in which we are checking all conditions
I have done in the same way. I am very lazy. So decided not to go for seperate initialization, but just kept if(i==0) d[i][j]=false else if (j==0) d[i][j]=true. I think the only disadvantage of doing it is that each single time when the decision needs to be taken, we will check for i==0 and j==0 for all elements, which can be avoided if we initialize them separately. I think this is the reason maybe to initialize it separately first.
Very nicely explained!
Thanks :)
03:05 In the second condition, we are taking the value of 3 and computing 5-3 = 2, but why its sum - set[n-1] when set[n] is the current element.
Here N is length of an array, we need to acess last element of an array, so n-1 will give acess to the last element
crystal clear explanation...
Thanks :)
Thanks for the clear explanation. Please make some videos on bitmasking. There are very few available in youtube about bitmasking. Could you please let me know whether this problem can be solved using bit masking?
I will let you know once i try.
@@techdose4u thank you for the reply. with the dynamic programming approach, Can we find the total no of subsets that will form the given sum?
you can also say that 0 is present in every subset so thats why thats column is true
Is it necessary for array to be sorted?
Actually you don't need a sorted array. The elements can be in any order, it will start taking elements from 1st postion in the 1st row till last position element in last row.
Moreover, if you can notice, set is an unordered collection of elements. So we should not be concerned about the order but only the elements.
i think YES , you should start with smallest element first to reach the solution
I think, For backtracking array no need to be sorted because we are checking for each and every possibility.
@@bmuralikrishna8054 For both the solutions the aray need not to be sorted. Here in example he has just taken the sorted array
super super super amazing thx!!
Can you please explain why we are considering 1 row above? that logic I am not clear with
I will show this in one DP problem soon.
I still cannot understand when do we need to have dp[n+1][target+1]? how have decided the range?
We don't use 0th row and column. So we take 1 extra size
Great ☺️ Thanks for the video
Welcome :)
At 2:51, is it required to search the 2nd option if the 1st returns true?
Also, I wanted to thank you so much for the content. Solving this by hand and following along, helped me understand this concept.
Great explanation!!
Thanks bhai :)
but what if i want to find all the subsets from a set, which gives a sum equal to a given value? (using DP, as it just tells me if its possible to get a subset or not i.e. true or false)
You would need to iterate this table to find all the "T" cells and print arr[i-1] of those cells.
Hi there, this is your code describing how to determine if True or False for each cell in matrix
subset[i][j] = subset[ i - 1][ j ] | |
subset[i - 1][j - set[i - 1]];
The second half after the OR operator represents what happens when we SELECT the I'th Element.
My question is why is it j - set[i - 1] and NOT j - set[ i ].
Shouldn't we minus the current sum(j) by the current 'weight' (set[i]) of the i'the element and see if the first i - 1 elements can sum up to it?
Same thoughts! I think he made mistakes.
The reason for that is because first the table size is num of elements+1 and subsetsum+1. The first element and the sum are going to be zeroth element and zeroth subsetsum. Hence, whenever we consider the formula, we need to go with -1.
You can run the code and you will be able to see that it works in this manner.
//My Code
public static boolean isSubSetSumTabulation(int arr[],int subSetsum){
int n=arr.length;
boolean dp[][]=new boolean[n+1][subSetsum+1];
for(int i=0;i
Great video, thank you!
Welcome
thankkkkuuuu so much sir
Welcome :)
Can we find max size of subarray having a sum k say 5 by this technique
Good explained
Thanks
Understand the significance, backtracking(bt) vs dp
n : 10 sum : 100070 dp/bt ratio : 977.24609
n : 20 sum : 3200140 dp/bt ratio : 61.03783
n : 30 sum : 24300210 dp/bt ratio : 0.67894
n : 40 sum : 102400280 dp/bt ratio : 0.00373
n : 50 sum : 312500350 dp/bt ratio : 0.00001
n : 60 sum : 777600420 dp/bt ratio : 0.00000
n : 70 sum : 1680700490 dp/bt ratio : 0.00000
n : 80 sum : 3276800560 dp/bt ratio : 0.00000
n : 90 sum : 5904900630 dp/bt ratio : 0.00000
n : 100 sum : 10000000700 dp/bt ratio : 0.00000
Note : dp/ bt = (n*sum) / (2**n), n=no of elements
awesome! Thank you for the work!
wow thats great job
Thanks
This solution also possible with O(n) space.
Yes correct. You can do with just storing a row.
How will the solution change, is the set is allowed to have negative numbers..
If number of elements are high and the value are also high, (arr= [23423343, 33427262,62829927] ] ) do we have any other approach apart from exponential complexity?
Recursion is exponential in No of elements and DP is exponential in Target SUM. If one is very large as compared to the other then you can apply the alternate methods.But, if both are large, maybe you can get idea from here: stackoverflow.com/questions/18432759/subset-sum-for-large-sums
Sir any way to print the subsets using dynamic programming?..
thanks 🙂
Welcome
Thank you so much
same as knapsack problem instead of or u can use 0,1 and maximize
Yea
How can I print the Subest using dynamic programming?
Awesome
Hi I think you might make a mistake when explaining:
ISS(set, n, sum) = ISS(set, n - 1, sum) || ISS(set, n-1, sum-set(n - 1)) ;
shouldn't it be:
ISS(set, n, sum) = ISS(set, n - 1, sum) || ISS(set, n-1, sum-set(n )) ; ?
the latter case is when we are including the nth element which means we should substract set[n] from set
If the indexing is same as numbering then it will be same otherwise the other way around. Depends on how we assumed indexing and numbering coz numbering may start from 1 but index always starts at 0. I hope this might help :)
@@techdose4u Aha I see thanks! this makse perfect sense.
int n = nums.length;
then
memo[c] = memo[c] || memo[c - nums[item]];
or
int n = nums.length + 1;
then
dp[s] = dp[s] || dp[s - nums[item - 1]];
@@user-qo8bj9en4r This is correct. Initalization is what's doing this.
i could understand the dp but recursion i understood
sir did u make video on how to find all the possible subset of sum ? if u made then please comment that video link,Thank you
No I didn't. I think you are asking about bruteforce technique right?
Just wanted to ask is this series enough for placement preparation of dp questions?
Follow my DP playlist Newbie to Expert. If you do that then you have covered the required placement topics. Now just need to keep on practice while doing other problems.
I think the reason why we hop to [j-nums[i-1] th column and [i-1]th row needs to be explained in a better way. It should clearly say that that we are trying to simulate the recursive call stack of the inclusion of the first element, where we call subsetSum(nums, index - 1, sum - nums[index]). This recursion call HITS a base case of sum = 0 with no other element left in the array to choose from. Hence the row 0 and it gives the same result as our recursion base case.
It's not very intuitive as per the current explanation. You have to go back to the recursion to drive home the point.
how to find which element is added to make SUM??
How to display the subsets that sum to the given value?
🔥🔥🔥🔥🔥🔥🔥🔥🔥
:)
what are the changes made in the code from naive approach I did not get you..
and Sir please explain how to print in backtracking approach I am unable to get it.
THANK YOU!!
Welcome
great video!
Thanks :)
Bhaiya if the sum is very large , say like 10^8 or 9 then how can we solve it ???? 🤔🤔🤔🤔🤔
You're a BOSSSS!
In the DP approach, how would we print the subset as well if we wanted to?
Simple. Whenever the cell is true, you will just need to print arr[i-1].
sir,By the way how to print those subsets in backtracking..kindly help sir
In backtracking method, as soon as as you get your SUM = 0 then keep a return flag , make it true and when you return back to parent node then you will get your flag set and so you will understand that current node lies in the path of finding the subset. So whatever choice you made (you chose or you left the current node), you will stick to it. If you had not included the current node to find sum, then final set will exclude that element. This is the process for backtracking method.
Can u plz say which app is using for white board sir