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

4 жыл бұрын

Welcome :)

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

3 жыл бұрын

Welcome :)

the best of the explaination i had seen so far

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

3 жыл бұрын

Thanks for your motivation bro :)

One of the best explanations of subset sum problem!

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

@techdose4u

4 жыл бұрын

Welcome :)

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

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

3 жыл бұрын

Thanks :)

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

@techdose4u

4 жыл бұрын

Welcome :)

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

@techdose4u

3 жыл бұрын

Thanks for supporting us ❤️

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.

Very good and clear explanation! Thank you!

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

4 жыл бұрын

Welcome :)

@aayush5474

4 жыл бұрын

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

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

@techdose4u

3 жыл бұрын

Thanks

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

3 жыл бұрын

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 😆

Amazing explanation bro, can't go without liking.

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

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

@techdose4u

3 жыл бұрын

Thanks 😊

Great job, explaining this! 🎉

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

@techdose4u

3 жыл бұрын

Thanks

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?

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

@techdose4u

3 жыл бұрын

Thanks :)

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

@techdose4u

3 жыл бұрын

Welcome 😊

@ritiksolanki6267

3 жыл бұрын

Rona kya isme🙄😂😂

@spetsnaz_2

3 жыл бұрын

@@ritiksolanki6267 khushi k aansu

I was looking for such videos. Really helpful 👌👍

@techdose4u

4 жыл бұрын

Thanks :)

Great video! :) Liked and subscribed!

@techdose4u

2 жыл бұрын

Thanks 😊

super super super amazing thx!!

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

4 жыл бұрын

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

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

@techdose4u

4 жыл бұрын

Thanks

Thanks a lot sir. Now I clearly understood.

@techdose4u

3 жыл бұрын

Welcome :)

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

@techdose4u

2 жыл бұрын

For sure ❤️

Very well explained! You definitely need more likes..

@techdose4u

3 жыл бұрын

Thanks for liking ❤️

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

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

@techdose4u

4 жыл бұрын

Thanks bro:)

@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

most underated channel

@techdose4u

3 жыл бұрын

😅

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

@techdose4u

4 жыл бұрын

Welcome :)

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

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.

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

You're a BOSSSS!

Thanks for this magical explanation.

@techdose4u

3 жыл бұрын

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.

@techdose4u

3 жыл бұрын

Okay sure

Great video, thank you!

@techdose4u

3 жыл бұрын

Welcome

Appreciate such a clean explanation

@techdose4u

3 жыл бұрын

Thanks

great explanation... Thank you, sir.

@techdose4u

4 жыл бұрын

Welcome :)

Thank you so much

really best lecture perfect!!..

@techdose4u

2 жыл бұрын

Thanks 😊

This is some nice stuff explained superbly!

@techdose4u

4 жыл бұрын

Thanks

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

@techdose4u

4 жыл бұрын

:)

Next level Explanation ✨

@techdose4u

3 жыл бұрын

Thanks :)

Very nicely explained!

@techdose4u

4 жыл бұрын

Thanks :)

Well illustrated. Thanks

@techdose4u

3 жыл бұрын

Welcome :)

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

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

3 жыл бұрын

You can just maintain a row to do that

How can I print the Subest using dynamic programming?

crystal clear explanation...

@techdose4u

4 жыл бұрын

Thanks :)

Great explanation!!

@techdose4u

3 жыл бұрын

Thanks bhai :)

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

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 ☺️ Thanks for the video

@techdose4u

3 жыл бұрын

Welcome :)

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

Very well explained

@techdose4u

2 жыл бұрын

Thanks

how can you use this on lc 32 combination sum?

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

3 жыл бұрын

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

@saravanan925

3 жыл бұрын

Thank you brother

@techdose4u

3 жыл бұрын

👍

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

can you tell me how to print elements of subset

crystal clear sir, 🙌🙌👏

@techdose4u

3 жыл бұрын

Thanks :)

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

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

@techdose4u

2 жыл бұрын

👍🏼

THANK YOU!!

@techdose4u

3 жыл бұрын

Welcome

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

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.

great video!

@techdose4u

4 жыл бұрын

Thanks :)

wow thats great job

@techdose4u

3 жыл бұрын

Thanks

thankkkkuuuu so much sir

@techdose4u

3 жыл бұрын

Welcome :)

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

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

4 жыл бұрын

I will let you know once i try.

@bmuralikrishna8054

4 жыл бұрын

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

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

@techdose4u

3 жыл бұрын

I will show this in one DP problem soon.

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].

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

3 жыл бұрын

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

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.

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

@techdose4u

3 жыл бұрын

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

thanks 🙂

@techdose4u

3 жыл бұрын

Welcome

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

3 жыл бұрын

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,By the way how to print those subsets in backtracking..kindly help sir

@techdose4u

4 жыл бұрын

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.

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

@techdose4u

3 жыл бұрын

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.

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

@techdose4u

3 жыл бұрын

Sure :)

@akankshasharma148

3 жыл бұрын

@@techdose4u Thanku🙏

Good explained

@techdose4u

3 жыл бұрын

Thanks

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

understood :)

@techdose4u

3 жыл бұрын

Nice :)

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

3 жыл бұрын

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

sir can i solve it using hashmap?

Di they fixed error 12?

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

2 жыл бұрын

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

🔥🔥🔥🔥🔥🔥🔥🔥🔥

@techdose4u

3 жыл бұрын

:)

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

@techdose4u

3 жыл бұрын

Dint check 523. This is the classic problem.

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

@techdose4u

3 жыл бұрын

Yea

how to print the subsets

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.

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

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.