DP 14. Subset Sum Equals to Target | Identify DP on Subsequences and Ways to Solve them
ฝัง
- เผยแพร่เมื่อ 8 ก.ค. 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
![[4K] BABYMONSTER(베이비몬스터) “FOREVER” Band LIVE Concert “영원히” 베몬만을 사랑하게 되…💗 [it’s KPOP LIVE 잇츠라이브]](http://i.ytimg.com/vi/TQfC0xdpiw4/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
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
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.
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?
Understood, Very well explained. the best DP playlist. Thanks for taking time and making the videos.
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. 🙏🙌
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
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.
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.
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.
Your energy and passion for breaking it down is commendable… thanks
in tabulation
why dp[0][arr[0] ] is equal to true
understood
Tabulation burra padu . Super oo
Understood. Brilliantly explained. You clear the concepts to the core.
Had trouble understanding bottom up approach till I saw this vid. Thanks a lot!
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] ??
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
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!
understood, this is the best dp playlist indeed
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..
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 ♥
UNDERSTOOD..................Thank You So Much for this wonderful video..........🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
He is probably one of the most genius guy I ever come across
"what's bottom up ulta ulta"
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.
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 ❤
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 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
In two days, I am able to convert my recursive solutions to iterative. All thanks to you!
Understood 💯💯 Great Explanation. Thank you very much for all you efforts🔥🔥
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 ?
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.
it took time to understand it but it worth every second
fabulous explaination thank you soo much for these high quality videos..🤗
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
[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]
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?
I understood all the concepts that you taught in this lecture
Understood, Thank you so much.
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.
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...
Understood! I truly appreciate for your explanation!!!
Thanks Striver for great solution
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.
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
Best DP series so far
Last one was greattt 🔥
GOAT
Time complexity:
Recursion: 19:37
Memoization: 22:20
Space optimization: 36:44
Code:
Recursion: 29:32
Memoization: 30:52
Tabulation: 33:15
Understood! Thanks man!
Understood, sir. Thank you very much.
best explanation.... drawing recursion tree really helps understand better !
Understood. Brilliantly explained.
Understood! Thank you for the explanation.
Understood !!!! ❤️
Thank you for this wonderful video
Very helpful! Thank you very much!
bro doing gods work
understood Sir .From DP Video 1 I was watching video in that mean time
Thank you Striver bhai..
Sir, you are amazing. Understood. ♥
understood bhaiya becoz of u i am able to solve dp questions easily now .
Understood. Thankyou sir
Understood. Thank you ❤️
UNDERSTOOD! THANK YOUUU
Words of striver matter more than looking screen ❤
Understood and thanks for amazing content you provide
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
Understood!!
Thank you
Understood. Thanks for the valuable information.
Thank you so much!
Simply Amazing!!
Awesome Explanation. Understood!
Understood and Thank You Striver!!
UNDERSTOOD... !
Thanks striver for the video... :)
Thank you bhaiya for these wonderful videos ❤️❤️
this is the amazing dp journey to me.
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
Understood. Superb explanation!
Thank you, understood
understood, thank u, sirji.
You are awesome. Understood!!
Understood!Thank you very much!
Amazing and understood 🔥
Understood bhaiya... Thanks😊
understood very well❤
Understood. Thank you for this.
Understood, good content
Understood Sir Thank you very much
understood sir!!
Understood bhaiyya.......
Understood ❤
understood
this and the last question were not easy
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.
Us ! It was fun to enter into something new!
understood. thank you.
best vdo ever
thanks
Understood Sir, Thank you so much :)
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
understood sir
great explanation