Тёмный
No video :(

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

take U forward
Подписаться 635 тыс.
Просмотров 367 тыс.
50% 1

Lecture Notes/C++/Java Codes: takeuforward.org/data-structu...
Problem Link:bit.ly/3ukNmRZ
Pre-req for this Series: • Re 1. Introduction to ...
a
Make sure to join our telegram group for discussions: linktr.ee/takeUforward
Full Playlist: • Striver's Dynamic Prog...
In this video, we solve the problem subsets sum equal to K. This problem is the first problem on DP on Subsequences Pattern. Please watch this video to have a clear concept of take/notTake concept.
If you have not yet checked our SDE sheet, you should definitely do it: takeuforward.org/interviews/s...
You can also get in touch with me at my social handles: linktr.ee/takeUforward

Опубликовано:

 

8 авг 2024

Поделиться:

Ссылка:

Скачать:

Готовим ссылку...

Добавить в:

Мой плейлист
Посмотреть позже
Комментарии : 1 тыс.   
@takeUforward
@takeUforward 2 года назад
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
@riderpd09 2 года назад
Just love the meta of solving subsequences by "take" and "not-take" :) A big US!!!
@amishasahu1586
@amishasahu1586 2 года назад
Understood Sir
@kiranbari6284
@kiranbari6284 2 года назад
i think subset sum also can be done using only one array......as you did in knapsack problem....
@anonymousvoid6356
@anonymousvoid6356 2 года назад
Huge big understood!!!!
@manishprajapati8544
@manishprajapati8544 2 года назад
mera full support bhai 👍👍👍
@ankitadas5833
@ankitadas5833 2 года назад
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
@takeUforward 2 года назад
Thanks for noticing ♥️
@RajeevKumar-fb3in
@RajeevKumar-fb3in 2 года назад
😱😱
@RajeevKumar-fb3in
@RajeevKumar-fb3in 2 года назад
You also saw his video 02:53 AM😱
@shiblijamal8544
@shiblijamal8544 10 месяцев назад
3am is like heaven time to code❤
@lakshsinghania
@lakshsinghania 9 месяцев назад
@@shiblijamal8544 can't stress more on this
@tanmay9928
@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.
@charanteja2407. 11 месяцев назад
Can anyone list those key points here
@ParodyCSEDept
@ParodyCSEDept 4 месяца назад
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!
@swapan6785
@swapan6785 7 месяцев назад
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.
@k4ranjith
@k4ranjith 2 года назад
Understood, Very well explained. the best DP playlist. Thanks for taking time and making the videos.
@kevinthant2952
@kevinthant2952 7 месяцев назад
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. 🙏🙌
@priyanshubansal6820
@priyanshubansal6820 2 года назад
This is the best dp solving technique that I have ever seen. thank you for giving us this wonderful playlist
@chetanthakral5322
@chetanthakral5322 2 года назад
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
@takeUforward 2 года назад
Corrected in the next video. Thanks.
@elements8630
@elements8630 2 года назад
I was confused about this part. thanks, bud!
@rishabhtater889
@rishabhtater889 2 года назад
but why in the first place dp[0][arr[0]]=true is mentioned?
@pk4288
@pk4288 2 года назад
@@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
@rishabhtater889 2 года назад
@@pk4288 so in tabulation, we are assuming it to be true only? Then we'll move forward?
@MohammadKhan-ld1xt
@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..
@smitboraniya6752
@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.
@nagame859
@nagame859 11 месяцев назад
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 👏 🙌 🙏
@lambar0
@lambar0 Год назад
Your energy and passion for breaking it down is commendable… thanks
@user-cl3un2qx7s
@user-cl3un2qx7s Месяц назад
in tabulation why dp[0][arr[0] ] is equal to true
@user-cl3un2qx7s
@user-cl3un2qx7s Месяц назад
understood
@nityanandbhaskar2155
@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
@devsrivastava2300 Год назад
that won't be an edge case as initially the whole dp is marked false in tabulation method
@Pirates571
@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
@jayendraawasthi2646 Год назад
@@devsrivastava2300 assume arr[0] = 1000 and target is 10. It will give error.
@devsrivastava2300
@devsrivastava2300 Год назад
Oh ok got it , thanks
@muditkhanna8164
@muditkhanna8164 10 месяцев назад
keen observation.
@oliverlowcy
@oliverlowcy 2 года назад
Had trouble understanding bottom up approach till I saw this vid. Thanks a lot!
@aarushirai6374
@aarushirai6374 2 года назад
Understood. Brilliantly explained. You clear the concepts to the core.
@dsp-io9cj
@dsp-io9cj 10 месяцев назад
dp[0][arr[0]]=1; in this what if arr[0] is greater than target, coz given constraints are arr[i]
@AD-fs6hr
@AD-fs6hr 3 месяца назад
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.
@roshangupta8161
@roshangupta8161 Год назад
Understood each and everything!!!Thanks for this amazing Dp series.
@Abhijeet-st4bj
@Abhijeet-st4bj Год назад
bhai why dp[ind+1][target+1]?? why not dp[ind+1][target+1]??
@deviprasad_bal
@deviprasad_bal Год назад
@@Abhijeet-st4bj do you mean why not dp[ind][target] ??
@rijumondal6876
@rijumondal6876 7 месяцев назад
He is probably one of the most genius guy I ever come across
@SriAdiNarayanaReddySabbella
@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 ❤
@arpitrajput6424
@arpitrajput6424 2 года назад
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
@ajith4249
@ajith4249 10 месяцев назад
Tabulation burra padu . Super oo
@lalitchahar1068
@lalitchahar1068 6 месяцев назад
it took time to understand it but it worth every second fabulous explaination thank you soo much for these high quality videos..🤗
@stith_pragya
@stith_pragya 7 месяцев назад
UNDERSTOOD..................Thank You So Much for this wonderful video..........🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
@zeroanims4113
@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
@GauravThinks 6 месяцев назад
yahi dhund raha tha mai bhai ♥
@Rohit-zk1lz
@Rohit-zk1lz Год назад
"what's bottom up ulta ulta"
@shivambajaj7640
@shivambajaj7640 3 месяца назад
In two days, I am able to convert my recursive solutions to iterative. All thanks to you!
@piyushsaxena6243
@piyushsaxena6243 2 года назад
understood, this is the best dp playlist indeed
@anything_jara_hatke5237
@anything_jara_hatke5237 2 года назад
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.
@aman9633
@aman9633 2 года назад
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
@takeUforward 2 года назад
Yes true, correctly pointer out. Thanks. For that reason we need to write another check condition.
@satyamraj2779
@satyamraj2779 Месяц назад
or rather you can just do this for(int i = 0; i
@priyanshuchouhan9845
@priyanshuchouhan9845 11 месяцев назад
the lecture was amazing . This took my concept of dp at next level.
@dharmeshpoladiya9047
@dharmeshpoladiya9047 2 года назад
Understood 💯💯 Great Explanation. Thank you very much for all you efforts🔥🔥
@RahulKushwah-sv9rh
@RahulKushwah-sv9rh 2 года назад
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
@takeUforward 2 года назад
Areh video th dekh lo :|
@RahulKushwah-sv9rh
@RahulKushwah-sv9rh 2 года назад
Woh toh smj aa hi jayegi bhaiya aap Padhye ho😀
@rahulpothula1902
@rahulpothula1902 2 года назад
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
@aaryan3461 2 года назад
same doubt
@codingachinilgtifirbhikrrh9009
@codingachinilgtifirbhikrrh9009 2 года назад
it is a reminiscence of the base condition which we used in recursion i.e. if(i==0)return arr[0] = target
@georgemullarj
@georgemullarj 2 года назад
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
@abhishekgururani6993 2 года назад
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
@tusharsahu397 2 года назад
Same Doubt...........as arr[0] can be any large value then how can we take it as index of a fixed size dp??
@rapidreplay6062
@rapidreplay6062 5 месяцев назад
understood Sir .From DP Video 1 I was watching video in that mean time
@dakshjainth3212
@dakshjainth3212 28 дней назад
thank you sir for this amazing video and in-depth explanation "US"
@anything_jara_hatke5237
@anything_jara_hatke5237 2 года назад
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?
@amitghosh4548
@amitghosh4548 2 года назад
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
@sushant8686 2 года назад
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 ?
@ritikshandilya7075
@ritikshandilya7075 Месяц назад
Thanks Striver for great solution
@priyanshuchouhan9845
@priyanshuchouhan9845 11 месяцев назад
I understood all the concepts that you taught in this lecture
@adityajain1205
@adityajain1205 2 года назад
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...
@legendsoflife3955
@legendsoflife3955 2 года назад
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.
@ramyasree4986
@ramyasree4986 2 года назад
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
@sairam3351
@sairam3351 8 месяцев назад
Understood, Thank you so much.
@parthsalat
@parthsalat 2 года назад
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
@snipercool4169
@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
@pritamiitismdhanbad561 Год назад
one issue you have to also add else dp[i][j]=dp[i-1][j]
@radekszewczyk3603
@radekszewczyk3603 3 месяца назад
Understood! Thanks man!
@anikethdeshpande8336
@anikethdeshpande8336 Год назад
best explanation.... drawing recursion tree really helps understand better !
@sujalgupta6100
@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
@subhashpabbineedi7136 Год назад
I think, if there is 1 based indexing we take n+1 or else n
@harishchandra8057
@harishchandra8057 Год назад
@@subhashpabbineedi7136 correct
@Codebreaker0702
@Codebreaker0702 Год назад
Did u get your answer ?
@sujalgupta6100
@sujalgupta6100 Год назад
@@Codebreaker0702 yes kunal , I take n+1 size everytime, because it works fine most of the time.
@deviprasad_bal
@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.
@parthsalat
@parthsalat 2 года назад
Time complexity: Recursion: 19:37 Memoization: 22:20 Space optimization: 36:44 Code: Recursion: 29:32 Memoization: 30:52 Tabulation: 33:15
@abdallaalhag4425
@abdallaalhag4425 7 месяцев назад
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
@mr.jacker3951
@mr.jacker3951 Год назад
was Asked in Google last year in Interview
@user-pi3yv8hj1v
@user-pi3yv8hj1v 10 месяцев назад
Very helpful! Thank you very much!
@udayprakashharsh2805
@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
@disunique6107
@disunique6107 2 года назад
Last one was greattt 🔥 GOAT
@MukeshKumar-cc3uh
@MukeshKumar-cc3uh 6 месяцев назад
Sir, you are amazing. Understood. ♥
@bahveshjain1730
@bahveshjain1730 2 года назад
understood bhaiya becoz of u i am able to solve dp questions easily now .
@cinime
@cinime 2 года назад
Understood! I truly appreciate for your explanation!!!
@SajanKumar-ec2us
@SajanKumar-ec2us 3 месяца назад
understood ! **please discuss in sort video how you became a expert coder?
@sachinNotOut
@sachinNotOut 6 месяцев назад
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
@Pandey_Puja
@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]
@soubhikghosh6564
@soubhikghosh6564 Год назад
Best DP series so far
@pabitrakb5291
@pabitrakb5291 Год назад
Understood !!!! ❤️ Thank you for this wonderful video
@aps8874
@aps8874 Месяц назад
Thank you so much!
@madhav3444
@madhav3444 2 года назад
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
@hashcodez757
@hashcodez757 10 дней назад
"UNDERSTOOD BHAIYA!!"
@parthsalat
@parthsalat 2 года назад
Understood! Now you can peacefully go back to sleep 😴
@AngadSingh97
@AngadSingh97 6 месяцев назад
Thank you Striver bhai..
@105avniuplabdhee5
@105avniuplabdhee5 9 месяцев назад
understood
@shreyashtech8556
@shreyashtech8556 4 месяца назад
bro doing gods work
@koushalsharma7041
@koushalsharma7041 2 года назад
Understood! Thank you for the explanation.
@ranasauravsingh
@ranasauravsingh 2 года назад
UNDERSTOOD... ! Thanks striver for the video... :)
@kaustubhrai312
@kaustubhrai312 2 года назад
Understood. Brilliantly explained.
@rushyya
@rushyya 10 месяцев назад
UNDERSTOOD! THANK YOUUU
@viraj701
@viraj701 3 месяца назад
can we use the combination sum ii (recursion L-9) approach to solve this problem using dp?
@ayushpatel2171
@ayushpatel2171 2 года назад
Is there a similar question also present on leetcode?
@akku5529
@akku5529 11 месяцев назад
let arr = [1,2,4] and target = 0 then according to the recursive solution if(target == 0) return true. Hence this will return true which is wrong in this case because there exist no such subsequence apart from an empty subsequence. I'm confused if we can take empty subsequence into account. Please explain @takeUforward
@ratinderpalsingh5909
@ratinderpalsingh5909 2 года назад
Understood, sir. Thank you very much.
@priyanshuchouhan9845
@priyanshuchouhan9845 11 месяцев назад
this is the amazing dp journey to me.
@ScienceSeekho
@ScienceSeekho 2 года назад
For tabulation, In second for loop why are we going upto target? for(int ind = 1; ind
@manishkumar-nh9jo
@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.
@sukuna905
@sukuna905 Месяц назад
understood sir!!
@yashkhatwani3198
@yashkhatwani3198 Год назад
Understood and thanks for amazing content you provide
@minhthang93
@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
@geetanjalikarma958
@geetanjalikarma958 10 месяцев назад
Understood!! Thank you
@azizazmir2159
@azizazmir2159 Год назад
Words of striver matter more than looking screen ❤
@prasannasippa5962
@prasannasippa5962 2 года назад
Understood thank you so much but am not able to solve the variation of this question in leetcode which is returning the count of subset sum equals to K.
@shivangpandey9943
@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
@RoyBoyLab 10 месяцев назад
yes
@Hrushi_2000
@Hrushi_2000 10 месяцев назад
Understood. Thankyou sir
@boomburstshorts2347
@boomburstshorts2347 Год назад
why we have taken target + 1 while constructing vector .......dp ?
@mridul.7183
@mridul.7183 7 месяцев назад
because else only we will be able to store till target-1. but to store till target, we took target+1.
@deonarayanchoudhari5237
@deonarayanchoudhari5237 2 года назад
Understood and Thank You Striver!!
@vikasbagri1225
@vikasbagri1225 Год назад
understood this and the last question were not easy
@iamokpara
@iamokpara 9 месяцев назад
You are awesome. Understood!!
@vedantgitte784
@vedantgitte784 10 месяцев назад
Understood, good content
@Harshit126
@Harshit126 2 года назад
Understood. Thanks for the valuable information.
@sugandhm2666
@sugandhm2666 2 года назад
Can we expect by February end, the entire dp playlist will be completed ?
@lavanyam3224
@lavanyam3224 4 месяца назад
In the space optimization step, we're assigning prev = cur, It is not a constant operation right? We're making a copy of cur and saving it in prev which takes O(target+1). Since we're doing it inside the loop, does the time complexity increase to O(N*target*target)?? To reduce the space complexity, are we compromising on the time complexity?
@MohanaKrishnaVH
@MohanaKrishnaVH 2 года назад
Awesome Explanation. Understood!
@umangbehl8152
@umangbehl8152 Месяц назад
great video
@NoBakwas
@NoBakwas Год назад
Thank you, understood
@prabhakaran5542
@prabhakaran5542 5 месяцев назад
Understood ❤
Далее
DP 15. Partition Equal Subset Sum | DP on Subsequences
9:43
8 patterns to solve 80% Leetcode problems
7:30
Просмотров 295 тыс.
Launching the best DSA Course + Platform
36:29
Просмотров 138 тыс.
DP 13. Cherry Pickup II | 3D DP Made Easy | DP On Grids
43:23
Count Subarray sum Equals K | Brute - Better -Optimal
24:09