DP 14. Subset Sum Equals to Target | Identify DP on Subsequences and Ways to Solve them

[@takeUforward]

I need your support, and you can do that by giving me a like, and commenting "understood" if I was able to explain you. Note: Please add a check for arr[0]

[@riderpd09]

Just love the meta of solving subsequences by "take" and "not-take" :) A big US!!!

[@amishasahu1586]

Understood Sir

[@kiranbari6284]

i think subset sum also can be done using only one array......as you did in knapsack problem....

[@anonymousvoid6356]

Huge big understood!!!!

[@manishprajapati8544]

mera full support bhai 👍👍👍

[@nityanandbhaskar2155]

Just a edge case correction. dp[0][arr[0]] could give out of bound exception if arr[0] > target. So use a check for that.

[@devsrivastava2300]

that won't be an edge case as initially the whole dp is marked false in tabulation method

[@Pirates571]

​@@devsrivastava2300 that will be an edge case if arr[0] is greater than the half of total sum then it will be out of bounds

[@jayendraawasthi2646]

@@devsrivastava2300 assume arr[0] = 1000 and target is 10. It will give error.

[@devsrivastava2300]

Oh ok got it , thanks

[@muditkhanna8164]

keen observation.

[@ParodyCSEDept]

Tbh in most of the previous 13 problems, I was intuitively able to guess the DP recurrence relation (without thinking about recursion and all). However for this question, intuition didn't kick in. Then, I remembered your words that if I can write a recursive solution for the problem then after following your steps, I will be able to reach the DP solution. So I did follow all the steps and yeah I really was able to reach the most optimal solution for this on my own. Hats off to you Striver! Understood!

[@anshpradhan1954]

You know what's cool about his teaching method, it actually works, he boiled down a complex topic like DP to mere steps which you just have to execute and reach the optimal solution, hats off to this man

[@VarshaSingh-hi2sb]

Why we are taking a 2 d dp array and not 1 since we are given a 1 d array? is it because both target and index are changing?

[@ParodyCSEDept]

@@VarshaSingh-hi2sb yes we consider all indices as well as all targets because they help us to reach the final answer.

[@prnvtj]

@@VarshaSingh-hi2sb yes. we choose the array dimensions based on the number of parameters changing.

[@tanmay9928]

Had to watch the video multiple times in order to fully understand this concept. In all seriousness, there are so many key points to be kept in mind when learning this concept.

[@charanteja2407.]

Can anyone list those key points here

[@ankitadas5833]

Understood! you ended the video by submitting space optimization code at Morning 02:53 AM,,,,, How much energy you have 😱😱😱😱. Hats off to your dedication.

[@takeUforward]

Thanks for noticing ♥️

[@RajeevKumar-fb3in]

😱😱

[@RajeevKumar-fb3in]

You also saw his video 02:53 AM😱

[@shiblijamal8544]

3am is like heaven time to code❤

[@lakshsinghania]

@@shiblijamal8544 can't stress more on this

[@dsp-io9cj]

dp[0][arr[0]]=1; in this what if arr[0] is greater than target, coz given constraints are arr[i]

[@AD-fs6hr]

Correct. I suppose the test cases in Coding Ninjas are made such that, target is always greater than first element. otherwise it would have thrown error.

[@chetanthakral5322]

I think he is missing a if case , if arr[0] >=k , then we would be getting a sigsegv runtime error. To remove that we can replace dp[0][arr[0]] = true; by if(arr[0]

[@takeUforward]

Corrected in the next video. Thanks.

[@elements8630]

I was confused about this part. thanks, bud!

[@rishabhtater889]

but why in the first place dp[0][arr[0]]=true is mentioned?

[@pk4288]

@@rishabhtater889 when we reach index 0 and target left is equal to arr[0] then only we will return true otherwise it will be false. so in tabulation we are initializing like that only

[@rishabhtater889]

@@pk4288 so in tabulation, we are assuming it to be true only? Then we'll move forward?

[@zeroanims4113]

27:58 this is a very important point to understand. I wrote the recursion slightly different from striver (i start from 0 -> N) meaning the top of my recursion is 0 and the bottom is N. So my dp bottom up nested loop is from n-1 going to 0, and will return dp[0[[k], it should still work code: bool dpWay(int n, int k, vector& arr){ vector dp(n+1, vector(k+1, false)); for (int i = 0; i = 0; i--){ for (int j = 1; j = arr[i]) take = dp[i+1][j-arr[i]]; dp[i][j] = skip || take; } } return dp[0][k]; } bool rcMemoWay(int i, vector& nums, int tar, vector& memo){ if (tar == 0) return true; if (i == nums.size()) return false; if (memo[i][tar] != -1) return memo[i][tar]; bool skip = rcMemoWay(i+1, nums, tar, memo); bool take = false; if (tar >= nums[i]) take = rcMemoWay(i+1, nums, tar - nums[i], memo); memo[i][tar] = skip || take; return memo[i][tar]; }

[@GauravThinks]

yahi dhund raha tha mai bhai ♥

[@parthsalat]

Time complexity: Recursion: 19:37 Memoization: 22:20 Space optimization: 36:44 Code: Recursion: 29:32 Memoization: 30:52 Tabulation: 33:15

[@bhoomikagajpal674]

Amazing!!!! Couldn't understand this for 6 years and 1 day you made it seem so easy!!!!!!

[@swapan6785]

Nicely explained! Had to do dry run multiple times for full understanding. It seems very tough to directly write tabulation/space optimization method, but easy when starting from recursion and following the order.

[@arpitrajput6424]

hey! we can add one more line to reduce further looping if we get our ans add if(dp[ind][k]==true)return true; at before end of second loop try it. vector dp(n,vector(k+1,false)); for(int i=0;i

[@mr.jacker3951]

was Asked in Google last year in Interview

[@GManiKarthik]

The first time, I tried to understand this concept by just watching the explanation 🧑‍🏫👀. I assumed I could skip deeper thinking and would grasp it in future lectures of this pattern 🤔➡📚. But no, my mind wasn’t cooperating 🤯. So, I decided to watch it again 📺, this time actively solving along with pen and paper ✍📄. After that, I mastered it and now feel very confident 💪✨! #Understood #DP14 #Hatsoff #Striver

[@ajith4249]

Tabulation burra padu . Super oo

[@MohammadKhan-ld1xt]

Before starting this dp series, I was really confused as to which playlist I should follow as there were many good playlist , but after listening to first 2 lectures, I knew that this is the best dp playlist I could ever find and this includes the paid courses too. I have paid courses but I prefer this. I am addicted to this playlist. Seriously!!! Hats of to you bhaiyya🔥Keep striving and good luck. Hope to see you on the right path..

[@k4ranjith]

Understood, Very well explained. the best DP playlist. Thanks for taking time and making the videos.

[@_sk99]

The way he teaches is fabulous!.... I love his enthu

[@SriAdiNarayanaReddySabbella]

Understood! Tabulation is tricky in this one a little bit. But, your explanation just made it so easy. Thank you so much for this amazing series ❤

[@VarshaSingh-hi2sb]

Why we are taking a 2 d dp array and not 1 since we are given a 1 d array? is it because both target and index are changing?

[@SriAdiNarayanaReddySabbella]

​@@VarshaSingh-hi2sbThe DP array that we take in a question is not at all related to the array that is given to us. As you said, since we can have multiple function calls for the same index with different targets, we are maintaining a 2D DP array. For example, in [1,2,3,4,5] with target 10, if we pick 5 at index 4, then from index 3 onwards, our target will be 10-5=5, if we don't pick 5, then target will remain the same i.e. 10. Since at the same index, function calls are made for different targets, to optimise them, we need to have a 2D array for every possible target at every possible index. Hope it helps!

[@rijumondal6876]

He is probably one of the most genius guy I ever come across

[@roshangupta8161]

Understood each and everything!!!Thanks for this amazing Dp series.

[@Abhijeet-st4bj]

bhai why dp[ind+1][target+1]?? why not dp[ind+1][target+1]??

[@deviprasad_bal]

@@Abhijeet-st4bj do you mean why not dp[ind][target] ??

[@kevinthant2952]

So far to me, you are the best explainer of algorithm questions on the whole Internet. Thank you so much for your amazing work on these explanation videos. 🙏🙌

[@lambar0]

Your energy and passion for breaking it down is commendable… thanks

[@HEMANTPORWAL-t7d]

in tabulation why dp[0][arr[0] ] is equal to true

[@HEMANTPORWAL-t7d]

understood

[@a_05_himanshu_akula31]

in tabulation base case we gotta take care of the case where arr[0] > k else dp[0][arr[0]] will go out of bound since dp is set to range of 0 to k

[@gudlaudaysai4571]

I am about to write this, glad you had asked it and i can confirm that my approach is correct

[@vishious14]

Quick question. Can you explain why we are marking dp[0][arr[0]] as true.

[@swapan6785]

@@vishious14 try doing dry run and you will get it. Basically dp[0] means we are checking only till first element (0th index in arr) and answer would be true only if arr[0] = target, otherwise false.

[@priyanshubansal6820]

This is the best dp solving technique that I have ever seen. thank you for giving us this wonderful playlist

[@shivambajaj7640]

In two days, I am able to convert my recursive solutions to iterative. All thanks to you!

[@rahulpothula1902]

Everything understood perfectly!! But a small doubt in tabulation: why did we directly write dp[0][arr[0]] = true without checking the condition if(arr[0] == k)??? Pls pls pls answer if anyone knows....🙏

[@aaryan3461]

same doubt

[@codingachinilgtifirbhikrrh9009]

it is a reminiscence of the base condition which we used in recursion i.e. if(i==0)return arr[0] = target

[@georgemullarj]

dp[0][arr[0]] means n=0, means only 1 element i.e., arr[0] present in array and the target is arr[0]. Since target and element is same it is true. I feel 1 based indexing is more easy to understand, see Aadity verma videos for it.

[@abhishekgururani6993]

Listen, in your base case for recursion you had condition that when "index will be 0" and "value of arr[0] will be equal to target" you'll return true. In tabulation, dp is represented like this : dp[index][target], so the value of dp when "index equals 0 and target equals arr[0]" is true;

[@tusharsahu397]

Same Doubt...........as arr[0] can be any large value then how can we take it as index of a fixed size dp??

[@stith_pragya]

UNDERSTOOD..................Thank You So Much for this wonderful video..........🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻

[@RahulKushwah-sv9rh]

Raj bhaiya rocks ☄☄☄ from beginning to this video I never felt that this is the same topic in which previously I faced a lot of problem to solved the question.

[@takeUforward]

Areh video th dekh lo :|

[@RahulKushwah-sv9rh]

Woh toh smj aa hi jayegi bhaiya aap Padhye ho😀

[@ramyasree4986]

in recursion time complexity is always no of changing states and possibilities (all stuffs) this we further reduce from exponential using memorization and with tabulation we remove stack space and with space optimisation we do reduce array dimension woww!!!! so clear explanation

[@aman9633]

What if n=1,k=5 and arr[0]=10 ,when we are doing pre[arr[0]] ,as arr[0]>k won't it go out of bounds??

[@takeUforward]

Yes true, correctly pointer out. Thanks. For that reason we need to write another check condition.

[@satyamraj2779]

or rather you can just do this for(int i = 0; i

[@smitboraniya6752]

At first I thought your methos is very obvious, but as we go further in dp playlist it proves to be much stronger tool to apply for solving tough problems.

[@Rohit-zk1lz]

"what's bottom up ulta ulta"

[@shivangpandey9943]

We can use a base case as if(target < 0) return false; this will help us to escape through edge case of bool take call

[@RoyBoyLab]

yes

[@amitghosh4548]

I've submitted the Top-Down version with 1D memo and still got accepted... vector memo; bool knapSack(int i, int sum, int K, vector &A) { if (i < 0) return false; if (sum >= K) return sum == K; if (memo[i] != -1) return memo[i]; if (knapSack(i - 1, sum + A[i], K, A) || knapSack(i - 1, sum, K, A)) memo[i] = 1; return memo[i] == 1; } bool subsetSumToK(int N, int K, vector &A) { memo.assign(N, -1); return knapSack(N - 1, 0, K, A); }

[@sushant8686]

i don't how this is working because for index we two choices how will you know which choice is giving me right and which is giving wrong ?

[@boomburstshorts2347]

why we have taken target + 1 while constructing vector .......dp ?

[@mridul.7183]

because else only we will be able to store till target-1. but to store till target, we took target+1.

[@parthsalat]

Note that striver changed the color of the curtains behind him from this video onwards. Hence from now onwards, all remaining videos of the playlist are very imp

[@lalitchahar1068]

it took time to understand it but it worth every second fabulous explaination thank you soo much for these high quality videos..🤗

[@snipercool4169]

[Java] Tabulation Solution : public class Solution { public static boolean subsetSumToK(int n, int k, int arr[]){ // Declaring dp array. boolean dp[][] = new boolean[n + 1][k + 1]; // If required sum = 0, answer always true. for (int i = 0; i

[@pritamiitismdhanbad561]

one issue you have to also add else dp[i][j]=dp[i-1][j]

[@nagame859]

understood! just the recurrence tree is enough to understand this problem.. which again.. you explained it in the best way in the recursive series.. props to you 👏 🙌 🙏

[@anything_jara_hatke5237]

When I took a 2D global vector of size n*k max values i.e 1e3*1e9, I am getting Segment error. But when I don't define it globally and take it as a parameter of function, than it is working fine, can I get its explanation please.

[@DhananjayKumar-bd2jg]

29:51 why we are taking size k+1 rather than k?

[@takeUforward]

One based indexing

[@legendsoflife3955]

he tried to do little bit good but the main intuition of this approach is missing, I still feel Aditya Verma explained it in a more better way.

[@oliverlowcy]

Had trouble understanding bottom up approach till I saw this vid. Thanks a lot!

[@adityajain1205]

Bhaiya you said that if it gets a true in recursion , further recursion will not take place. But we are returning in the end so i think full recursion will take place . Correct me if i am wrong...

[@dakshjainth3212]

thank you sir for this amazing video and in-depth explanation "US"

[@anything_jara_hatke5237]

Value of k is max 1e9 and N is 1e3, I don't think we can take 2D array as dp instead of vector, right?

[@epicsportsplay-c7w]

understood Sir .From DP Video 1 I was watching video in that mean time

[@sujalgupta6100]

i am little bit confused . when and why do we take size = n+1 sometimes while making dp[n+1 ] and sometimes we only take dp[n]

[@subhashpabbineedi7136]

I think, if there is 1 based indexing we take n+1 or else n

[@harishchandra8057]

@@subhashpabbineedi7136 correct

[@Codebreaker0702]

Did u get your answer ?

[@sujalgupta6100]

@@Codebreaker0702 yes kunal , I take n+1 size everytime, because it works fine most of the time.

[@deviprasad_bal]

in this question you can take n instead of n+1 , it'll work. basically we decide that by looking at the range of indices covered. here it was from 0 to n-1 , hence it covered n indices and hence we declare it as vectordp( n , vector(k+1,-1); k + 1, because target ranges from 0 to k.

[@priyanshuchouhan9845]

the lecture was amazing . This took my concept of dp at next level.

[@ScienceSeekho]

For tabulation, In second for loop why are we going upto target? for(int ind = 1; ind

[@manishkumar-nh9jo]

because array indexing is from 0 to n-1 for n sized array. here row represents the index of the array and col represents the target.

[@Pandey_Puja]

I didnt understand the logic behind below line of code Please note that it can happen that arr[0]>target, so we first check it: if(arr[0]

[@es_amit]

24:27 to convert easily recursive to tabulation Read below 1) if you have an array of size 0 and target 0, what will be the output ? ---- true because we have no elements and have no target. This is the case of dp[0][0] 2) if you have an array of any size and target 0, output -- true because we will not pick any of the elements in the array. case ---- dp[allrows][0]. 3) if you have an array of size 0 and target not equal to 0 , output ----- false because we have no elements to pick and achieve target ---- dp[1][allCols].

[@urvashiparmar4856]

Thanks!

[@priyanshuchouhan9845]

I understood all the concepts that you taught in this lecture

[@sachinNotOut]

you have already explained this in recursion playlist i think and this time you solved this by combination sum problem pattern from that recursion playlist

[@abdalla4425]

Did a dry run for the tabulation and space optimization that allowed me to understand the code, with a lil more practice, I will be able to come up with this without the video like how I did with recursion and the memoization solution! Thanks

[@bahveshjain1730]

understood bhaiya becoz of u i am able to solve dp questions easily now .

[@piyushmathpal4244]

Getting runtime error in tabulation approach? For those who are not able to run tabulation code in online editors (due to addition of edge case), add this check while initialising dp[0][arr[0]] :: if(arr[0] dp[ind][10].

[@sairam3351]

Understood, Thank you so much.

[@piyushsaxena6243]

understood, this is the best dp playlist indeed

[@MukeshKumar-cc3uh]

Sir, you are amazing. Understood. ♥

[@hashcodez757]

"UNDERSTOOD BHAIYA!!"

[@ritikshandilya7075]

Thanks Striver for great solution

[@minhthang93]

To more simplify the recursion to easy to understand: private static boolean recursion(int index, int target, int[] arr) { if (target == 0) return true; if (index < 0) return false; if (target < 0) return false; boolean take = recursion(index-1,target-arr[index],arr); boolean notTake = recursion(index-1,target,arr); return take || notTake; } But the way Striver do is help you save some recursion call -> his code will faster

[@parthsalat]

Understood! Now you can peacefully go back to sleep 😴

[@shashwatkumar6965]

In the second base case in tabulation if dp[0][arr[0]] = true, this means that at 0th index, the value stored in 0th index of arr will be true. So cant we do the same thing for all indices, ie dp[1][arr[1]] = true, similarly, dp[2][arr[2]] = true and so on. So, we can do this inside the for loop of the first base case for(int i = 0; i < n; i++){ dp[i][0] = true; dp[i][arr[i]] = true; }

[@madhav3444]

Why you started the outer for loop from index 1 to n and not 0 to n in the tabulated dp calculation 31:33 ? , I know it will give Runtime error but I am not getting intutuion for this. Thanks

[@rounakraj6276]

understood also the minor change in the last part of video is imp as it gives runtime error on leetcode if it is not changed.

[@rounakraj6276]

@Arjun search subset sum equal to target leetcode ... U will find the similar ques

[@koushikvss7638]

Is the corresponding question on leetcode 560. subarray sum equals K?

[@SajanKumar-ec2us]

understood ! **please discuss in sort video how you became a expert coder?

[@aarushirai6374]

Understood. Brilliantly explained. You clear the concepts to the core.

[@DilpreetSingh-cs7yz]

At 21:00 why there is +1 to index and target?

[@anikethdeshpande8336]

best explanation.... drawing recursion tree really helps understand better !

[@radekszewczyk3603]

Understood! Thanks man!

[@karthikmg3325]

Happy Teacher's day to Striver ❤🎉

[@TanviPoddar-f1k]

At 26:36, why is the index starting from 1? We haven't filled the entire 0th row, right? So shouldn't it start from 0?

[@MayankLC93]

space optimization is out of world !!!!!!!!!!!!😂😂😂 Aweosme Explanation ..

[@dharmeshpoladiya9047]

Understood 💯💯 Great Explanation. Thank you very much for all you efforts🔥🔥

[@abhijitbandgar8112]

Understood raj sir

[@piyushsharma2798]

25:06 i don't understood please someone explain

[@disunique6107]

Last one was greattt 🔥 GOAT

[@Morimove]

bhaiya aapko matrix table bana ke samjana chaiye tha. memoization mei sirf matrix bana dene se solve toh ho gaya bas samj hi nahi aaya ki kaise ho raha hai. laga jaise jaadu ho raha hai. fir kisi aur ki video dekhi toh pata lga ki kaise matrix table mei values fill hoti jaati hai aur subproblems hat jaate hai. space otimized vala bhi tabhi samj aaya jab matrix table bana ke dekhi. baki aap acha content toh banate hi ho toh keep going. 😄

[@priyanshuchouhan9845]

I have seen all previous videos of this dp series

[@udayprakashharsh2805]

Understood but having a slight doubt shouldnt we add if(notTake) dp[n][k] = true; as it is goona save us a lot of recursive calls if target is less than arr[n] thenpick call will be called even though there is not need for it

[@वीलवइंडिया]

Understood bhaiya... Thanks😊

[@ashokbabug47]

Even I know the solution I will see your videos because of your thought process

[@azizazmir2159]

Words of striver matter more than looking screen ❤

[@priyanshuchouhan9845]

this is the amazing dp journey to me.

[@ntgrn-pr5yx]

understood, thank you striver

[@vikasbagri1225]

understood this and the last question were not easy

[@kathanvakharia]

Understood...Completed 14/56

[@AngadSingh97]

Thank you Striver bhai..

[@gouravmukherjeee6950]

Thank you bhaiya for these wonderful videos ❤️❤️

[@shauryatomer1058]

thanks for this amazing content

[@student_03]

understood sir great explanation

[@shreyashtech8556]

bro doing gods work

[@viraj701]

can we use the combination sum ii (recursion L-9) approach to solve this problem using dp?

[@105avniuplabdhee5]

understood

[@parthsalat]

Continue from 22:30

[@shaik1525]

Understood bhaiyya.......