subset sum problem dynamic programming | backtracking sum of subsets

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.com/open?id=1qs4...
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 :)

[@aniketdubey7363]

the best of the explaination i had seen so far

[@VS-cy8oy]

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.

[@techdose4u]

Welcome :)

[@himalayagupta7744]

explained clearly , leaves no doubt in my mind , thank you sir.

[@techdose4u]

Welcome :)

[@alessandrocamillo4939]

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

[@techdose4u]

Welcome :)

[@mayankchauhan6680]

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.

[@techdose4u]

Thanks for your motivation bro :)

[@parthshah6343]

One of the best explanations of subset sum problem!

[@akhilkhubchandani2632]

The best explanation!. Made this problem seem so easy . Thanks a lot !

[@techdose4u]

Welcome :)

[@Nickel80]

Gave an applaud to this video and another video of yours. Keep up the good work :)

[@techdose4u]

Thanks for supporting us ❤️

[@abhimanyupagade4289]

Literally you are gem Thanks for your quality teaching keep it up

[@dancojocaru7217]

Very good and clear explanation! Thank you!

[@jhilikkundu3158]

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.

[@techdose4u]

Thanks :)

[@namisha6883]

Amazing content. Clearly visible that you are putting a lot of hard work.

[@techdose4u]

Thanks

[@taivinh1986]

I love this channel, thanks for it, i see i have ameliorated a lot, i will always support it

[@techdose4u]

Thanks 😊

[@anandakrishnan2685]

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.

[@iampatelajeet]

Amazing explanation bro, can't go without liking.

[@aayush5474]

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!

[@techdose4u]

Welcome :)

[@aayush5474]

@@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

[@Stuff395]

Great job, explaining this! 🎉

[@debanjanghosh5698]

I was looking for such videos. Really helpful 👌👍

[@techdose4u]

Thanks :)

[@CodeSuccessChronicle]

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 🙏🏻🥰

[@techdose4u]

Welcome :)

[@dineshothamkumar]

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 😆

[@AkashKumar-ym4gu]

This Channel Needs To Be Popular.. Absolutely Great Stuff.. ❤❤

[@techdose4u]

Thanks :)

[@sandeepnallala48]

one day sir you will become the biggest competitor for many other ppl teaching DSA sir. thanks a lot sir ..... : )

[@ShivamSingh-me1nb]

Great explanation, i have never seen anyone explain that much in you tube

[@techdose4u]

Thanks

[@ganeshkamath89]

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?

[@arunimadas3183]

Thanks a lot for this.❤️. I finally understood it 😭❤️ . Keep up the good work. :')

[@techdose4u]

Welcome 😊

[@ritiksolanki6267]

Rona kya isme🙄😂😂

[@spetsnaz_2]

@@ritiksolanki6267 khushi k aansu

[@maverickchinmaydas]

@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

[@tarungopal3065]

Superb and clear Explanation..You are very great at making these videos for free...

[@techdose4u]

Thanks

[@amarnaath5673]

IF YOU START AN ONLINE COURSE I LL BE THE FIRST ONE TO REGISTER

[@techdose4u]

Thanks bro:)

[@ashishkulkarni7674]

Hi sir, you teach everything very cleanly...please keep teaching us😊

[@techdose4u]

For sure ❤️

[@adityaojha2701]

Thanks a lot sir. Now I clearly understood.

[@techdose4u]

Welcome :)

[@jatinthakwani5370]

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.

[@techdose4u]

Yep. I will do it at some point of time.

[@aditisharma2552]

Very well explained! You definitely need more likes..

[@techdose4u]

Thanks for liking ❤️

[@dhruvgoel25]

Very well explained 👍 thank you sir..keep making such videos

[@techdose4u]

Welcome :)

[@dayanandraut5660]

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

[@vdengineering2666]

super super super amazing thx!!

[@neghatnazir1668]

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.

[@techdose4u]

Okay sure

[@Mandeepsingh-jo5cf]

Thanks for this magical explanation.

[@techdose4u]

Welcome :)

[@chaunguyen8202]

Great video! :) Liked and subscribed!

[@techdose4u]

Thanks 😊

[@ravikiranbaisani2145]

Appreciate such a clean explanation

[@techdose4u]

Thanks

[@letsdoeverythinginoneweek9398]

clean and crisp please make a video on time complexity ?how to find it ur explanations are great

[@christopherbeatty8836]

Great video, thank you!

[@techdose4u]

Welcome

[@sugatasaha4423]

great explanation... Thank you, sir.

[@techdose4u]

Welcome :)

[@tonyriddle7646]

most underated channel

[@techdose4u]

😅

[@soumeshnayak4546]

really best lecture perfect!!..

[@techdose4u]

Thanks 😊

[@niklas9562]

Very nice explanation in "Abob" (above) Video !

[@techdose4u]

:)

[@mirakabra2334]

Very nicely explained!

[@techdose4u]

Thanks :)

[@abhishekkumargupta3043]

This is some nice stuff explained superbly!

[@techdose4u]

Thanks

[@snehabaser3155]

Next level Explanation ✨

[@techdose4u]

Thanks :)

[@chrisogonas]

Well illustrated. Thanks

[@techdose4u]

Welcome :)

[@warrenbuffet2511]

You're a BOSSSS!

[@richardzhu2678]

Thank you so much

[@aakashsaini351]

crystal clear explanation...

[@techdose4u]

Thanks :)

[@BaljeetSingh-bx8yj]

Great explanation!!

[@techdose4u]

Thanks bhai :)

[@vinothrajg8576]

Great ☺️ Thanks for the video

[@techdose4u]

Welcome :)

[@ameynaik2743]

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?

[@techdose4u]

You can just maintain a row to do that

[@gauri360]

Very well explained

[@techdose4u]

Thanks

[@anubhavsaha6225]

Sir any way to print the subsets using dynamic programming?..

[@namanvijay3514]

crystal clear sir, 🙌🙌👏

[@techdose4u]

Thanks :)

[@nallasivakrishna5693]

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.

[@niksgupta36]

Would have been great if you explained memoization method before DP method. Good content btw! Thanks!

[@techdose4u]

👍🏼

[@akshayagrawal2222]

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

[@chainsinghpawar9138]

Can we find max size of subarray having a sum k say 5 by this technique

[@souvikghosh1285]

How can I print the Subest using dynamic programming?

[@durjaarai7737]

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.

[@i.vigneshdavid1698]

can you tell me how to print elements of subset

[@sindo1913]

THANK YOU!!

[@techdose4u]

Welcome

[@bmuralikrishna8054]

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?

[@techdose4u]

I will let you know once i try.

[@bmuralikrishna8054]

@@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?

[@labib28]

wow thats great job

[@techdose4u]

Thanks

[@raulherbert]

great video!

[@techdose4u]

Thanks :)

[@chakreshsingh]

How will the solution change, is the set is allowed to have negative numbers..

[@mohdhasnain3812]

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

[@dineshothamkumar]

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.

[@gauravbhisikar6381]

thankkkkuuuu so much sir

[@techdose4u]

Welcome :)

[@saravanan925]

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!!!

[@techdose4u]

Thanks. I will try to derive the recursive formula from now on.

[@saravanan925]

Thank you brother

[@techdose4u]

👍

[@dineshothamkumar]

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.

[@sazidimtiaz831]

thanks 🙂

[@techdose4u]

Welcome

[@akankshasharma148]

Great explanation sir!! Please also create a video on Sudoku solver🙏

[@techdose4u]

Sure :)

[@akankshasharma148]

@@techdose4u Thanku🙏

[@onestopplacement4917]

Can u plz say which app is using for white board sir

[@shaikzuhair8537]

Good explained

[@techdose4u]

Thanks

[@vikaspatel-fi8dl]

how to find which element is added to make SUM??

[@philipjames9194]

how can you use this on lc 32 combination sum?

[@physicsbyneha4210]

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)

[@dineshothamkumar]

You would need to iterate this table to find all the "T" cells and print arr[i-1] of those cells.

[@atharvamalhar7101]

Just wanted to ask is this series enough for placement preparation of dp questions?

[@techdose4u]

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.

[@rajkumarnagarajan2225]

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.

[@sasikumarvm5172]

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

[@MagicalCreationAviCreation]

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

[@techdose4u]

No I didn't. I think you are asking about bruteforce technique right?

[@debarunkumer2019]

How to display the subsets that sum to the given value?

[@PhoenixRisingFromAshes471]

sir can i solve it using hashmap?

[@vishnugovindan8550]

In the DP approach, how would we print the subset as well if we wanted to?

[@dineshothamkumar]

Simple. Whenever the cell is true, you will just need to print arr[i-1].

[@HariKrishnan-ff4hf]

sir,By the way how to print those subsets in backtracking..kindly help sir

[@techdose4u]

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.

[@pranavrajeshmadhani6260]

Can you please explain why we are considering 1 row above? that logic I am not clear with

[@techdose4u]

I will show this in one DP problem soon.

[@v.sreesairam9488]

understood :)

[@techdose4u]

Nice :)

[@bestsaurabh]

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?

[@techdose4u]

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

[@srimakarmakar4498]

Bhaiya if the sum is very large , say like 10^8 or 9 then how can we solve it ???? 🤔🤔🤔🤔🤔

[@shuchitam3868]

I still cannot understand when do we need to have dp[n+1][target+1]? how have decided the range?

[@techdose4u]

We don't use 0th row and column. So we take 1 extra size

[@letsdoeverythinginoneweek9398]

you can also say that 0 is present in every subset so thats why thats column is true

[@siddhantgupta958]

🔥🔥🔥🔥🔥🔥🔥🔥🔥

[@techdose4u]

:)

[@mindandmachine01]

Di they fixed error 12?

[@RTX_valorant]

same as knapsack problem instead of or u can use 0,1 and maximize

[@techdose4u]

Yea

[@michaelchan6144]

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?

[@chaunguyen8202]

Same thoughts! I think he made mistakes.

[@dineshothamkumar]

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.

[@dineshothamkumar]

You can run the code and you will be able to see that it works in this manner.

[@dineshothamkumar]

//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

[@rakshith3547]

Is this problem same as 523. Continuous Subarray Sum in Leetcode?

[@techdose4u]

Dint check 523. This is the classic problem.

[@kattelanithyasri7727]

how to print the subsets

[@uncodeyourself4473]

i could understand the dp but recursion i understood

[@deeptarkoroy6724]

What if we have negative elements?Will we not subtract the greater number?

[@dineshothamkumar]

I think if the numbers are negative, we will continue to subtract. The results may not be as expected though.