DP 14. Subset Sum Equals to Target | Identify DP on Subsequences and Ways to Solve them
HTML-код
- Опубликовано: 31 июл 2024
- 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
![[BLACKSWAN] ‘Roll Up’ Official Music Video](http://i.ytimg.com/vi/ulvCwyKrwqw/mqdefault.jpg)
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]
Just love the meta of solving subsequences by "take" and "not-take" :) A big US!!!
Understood Sir
i think subset sum also can be done using only one array......as you did in knapsack problem....
Huge big understood!!!!
mera full support bhai 👍👍👍
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.
Thanks for noticing ♥️
😱😱
You also saw his video 02:53 AM😱
3am is like heaven time to code❤
@@shiblijamal8544 can't stress more on this
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!
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. 🙏🙌
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.
Understood, Very well explained. the best DP playlist. Thanks for taking time and making the videos.
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 👏 🙌 🙏
This is the best dp solving technique that I have ever seen. thank you for giving us this wonderful playlist
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.
Can anyone list those key points here
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]
Corrected in the next video. Thanks.
I was confused about this part. thanks, bud!
but why in the first place dp[0][arr[0]]=true is mentioned?
@@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
@@pk4288 so in tabulation, we are assuming it to be true only?
Then we'll move forward?
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.
Understood. Brilliantly explained. You clear the concepts to the core.
Your energy and passion for breaking it down is commendable… thanks
in tabulation
why dp[0][arr[0] ] is equal to true
understood
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..
Had trouble understanding bottom up approach till I saw this vid. Thanks a lot!
it took time to understand it but it worth every second
fabulous explaination thank you soo much for these high quality videos..🤗
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
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.
that won't be an edge case as initially the whole dp is marked false in tabulation method
@@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
@@devsrivastava2300 assume arr[0] = 1000 and target is 10. It will give error.
Oh ok got it , thanks
keen observation.
UNDERSTOOD..................Thank You So Much for this wonderful video..........🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
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 ❤
dp[0][arr[0]]=1; in this what if arr[0] is greater than target, coz given constraints are arr[i]
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.
Understood each and everything!!!Thanks for this amazing Dp series.
bhai why dp[ind+1][target+1]?? why not dp[ind+1][target+1]??
@@Abhijeet-st4bj do you mean why not dp[ind][target] ??
understood, this is the best dp playlist indeed
He is probably one of the most genius guy I ever come across
Tabulation burra padu . Super oo
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];
}
yahi dhund raha tha mai bhai ♥
In two days, I am able to convert my recursive solutions to iterative. All thanks to you!
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
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.
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.
Areh video th dekh lo :|
Woh toh smj aa hi jayegi bhaiya aap Padhye ho😀
the lecture was amazing . This took my concept of dp at next level.
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
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....🙏
same doubt
it is a
reminiscence of the base condition which we used in recursion i.e. if(i==0)return arr[0] = target
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.
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;
Same Doubt...........as arr[0] can be any large value then how can we take it as index of a fixed size dp??
"what's bottom up ulta ulta"
Understood 💯💯 Great Explanation. Thank you very much for all you efforts🔥🔥
understood Sir .From DP Video 1 I was watching video in that mean time
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??
Yes true, correctly pointer out. Thanks. For that reason we need to write another check condition.
or rather you can just do this
for(int i = 0; i
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);
}
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 ?
I understood all the concepts that you taught in this lecture
best explanation.... drawing recursion tree really helps understand better !
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?
[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
one issue you have to also add else dp[i][j]=dp[i-1][j]
Understood, Thank you so much.
Understood! Thanks man!
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
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...
Very helpful! Thank you very much!
Last one was greattt 🔥
GOAT
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]
I think, if there is 1 based indexing we take n+1 or else n
@@subhashpabbineedi7136 correct
Did u get your answer ?
@@Codebreaker0702 yes kunal , I take n+1 size everytime, because it works fine most of the time.
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.
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.
Understood !!!! ❤️
Thank you for this wonderful video
thank you sir for this amazing video and in-depth explanation "US"
Time complexity:
Recursion: 19:37
Memoization: 22:20
Space optimization: 36:44
Code:
Recursion: 29:32
Memoization: 30:52
Tabulation: 33:15
Understood! I truly appreciate for your explanation!!!
Thanks Striver for great solution
Understood! Thank you for the explanation.
Sir, you are amazing. Understood. ♥
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
yes
why we have taken target + 1 while constructing vector .......dp ?
because else only we will be able to store till target-1. but to store till target, we took target+1.
understood bhaiya becoz of u i am able to solve dp questions easily now .
Awesome Explanation. Understood!
UNDERSTOOD! THANK YOUUU
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
Best DP series so far
Understood. Brilliantly explained.
bro doing gods work
Understood!!
Thank you
Thank you Striver bhai..
UNDERSTOOD... !
Thanks striver for the video... :)
Understood, sir. Thank you very much.
Understood and thanks for amazing content you provide
Understood. Thankyou sir
You are awesome. Understood!!
Understood and Thank You Striver!!
Thank you so much!
Understood!Thank you very much!
Understood. Thank you ❤️
understood
this and the last question were not easy
For tabulation, In second for loop why are we going upto target?
for(int ind = 1; ind
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.
maybe map will be better for tabulation and memorization because if we run a testcase will all elements are negative and target is negative too then the program will give `runtime error
Understood, good content
was Asked in Google last year in Interview
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
I am about to write this, glad you had asked it and i can confirm that my approach is correct
Quick question. Can you explain why we are marking dp[0][arr[0]] as true.
@@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.
this is the amazing dp journey to me.
Words of striver matter more than looking screen ❤
understood
can anyone help me , what modification should be done if we want to fix the number of elements which can be taken in the subsequence equal to a fix number like 3,4,10 etc
Understood. Thanks for the valuable information.
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
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
Us ! It was fun to enter into something new!
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.
Simply Amazing!!
Understood. Superb explanation!
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]
understood sir!!
Understood. Thank you for this.
"UNDERSTOOD BHAIYA!!"
Amazing and understood 🔥
understood ! **please discuss in sort video how you became a expert coder?