DP 21. Target Sum | DP on Subsequences
HTML-код
- Опубликовано: 10 фев 2022
- Lecture Notes/C++/Java Codes: takeuforward.org/dynamic-prog...
Problem Link: bit.ly/3swy5uL
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 of the target sum. This problem is the eighth problem on DP on the Subsequences Pattern. Please watch DP 18 before watching this.
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
damn man ! been watching all the videos of this playlist from the beginning, this is the best video so far !! and you striver. You are not only teaching how to do DP, but indeed how to think DP ! Kudos to you for this playlist.
Damn man ! been watching all the videos of this playlist from the beginning, this is the best video so far !! and you Striver. You are not only teaching how to do DP, but indeed how to think DP ! Kudos to you for this playlist.💌💌💌💌
I would have never thought, it can also be solved like this🤯. Thanks for this awesome playlist striver❤
I would have never thought of approaching this problem this way. Superb!
Thanks for this. I have watched and solved all the videos till now in this series.
Longest Common Subsequence and Longest Increasing Subsequence are much awaited.
You will be further directed to DP-17 when you watch DP-18 . This series is very well designed !
Its Recursion Go back and complete the part to get answer.
Higher Problem to lower subproblems
@@immortal6978 🤣
as soon as you wrote those S1 and S2 i figured out ohh hell yess this can be done by that approach! Best one till now!
Before watching your tutorial , I did solve this problem 🙂 using map(the naive recursive way and optimized with map). Here's the solution :
int f(int i, int target, vector& nums,
unordered_map& dp) {
if (i == nums.size()) {
if (target == 0)
return 1;
return 0;
}
string key = to_string(i) + "_" + to_string(target);
if (dp.find(key) != dp.end())
return dp[key];
int ways = f(i + 1, target - nums[i], nums, dp) +
f(i + 1, target + nums[i], nums, dp);
dp[key] = ways;
return ways;
}
int findTargetSumWays(vector& nums, int target) {
unordered_map dp;
return f(0, target, nums, dp);
}
Completed till here, please upload more videos. Thank you for such a quality content.
plus minus way.
int solve(int ind,int target,vector &nums,map &dp)
{
if(ind < 0)
{
//either you achieve the target or you don't achieve the target
if(target == 0)
return 1;
else
return 0;
}
if(dp.find({ind, target}) != dp.end())
{
return dp[{ind,target}];
}
int plus = 0;
int minus = 0;
plus = solve(ind-1,target + nums[ind],nums,dp);
minus = solve(ind - 1, target - nums[ind],nums,dp);
return dp[{ind, target}] = plus + minus;
}
int findTargetSumWays(vector& nums, int target) {
map dp;
return solve(nums.size()-1,target,nums,dp);
}
if we use a vector instead of a map it doesnt work can you please tell why
@@samnoitall9799 because we have a negative values so we can't put them in vector as we cant have -ve indexes
@@samnoitall9799 negative values
wow!!!!! awesome explanation, you are gods gift to the coding community🙏🙏🙏🙏🙏
In this question the target value can also be negative so it'll be better to take the min of sum+ target and sum - target as the length of prev and curr just because of the fact that, if target is negative then sum + target will be smaller than sum - target 😊
I never thought I could solve a dp problem :)...thanks legend!
Damn Damn Damn striver ,was not able to think that this question can be solved using this way.Mapping of problems is very much important.
Very nice study approaches. Thank you for this.
just fantastic. really getting enjoyed and feeling interested in coding and problem solving after your vidoes and approach sir. Thank you sir
understood bhai , thank you soo much for this entire dp series and all other dsa series as well;
😮😮😮Watching this solution made me go waahh!!!! Thank you bhaiya!!
Thanks striver. I solved this using normal recursion but you helped me to recognise the pattern of this problem.
for 2:30 to 2:50 you said exactly what everyone was thinking 😂😂
I was just studying from ur previous videos and got new♥️
The thought process is great bruh
You're genius man.
Understood very well.
BEST TEACHER EVERRRRR!!!
UNDERSTOOD... !
Thanks striver for the video... :)
understood at its best..
Understood. Thankyou Sir
understood thank you so much
chumeshwari explanation bhayia 🥰🥰🥰
Understoood so damn well 🔥🔥🔥🔥
Understood! I appreciate for your amazing explanation!!
Understood very well
UNDERSTOOD, thank you very much 😍
did it on my own, thnx
Once again I was able to solve it on my own. Thank you Striver
Understood bro ✌✌ and once again the power of observation is shown 🤩🔥🔥
Incredible 😮
amazing understood
I solved this problem yesterday and by considering +,- combinations, definitely had space complexity problems. This video gave me a different direction to think this same problem. Thank you!
give me recusion solution bro Im unable to do it .
@@gauravpoharkar9797
f(ind, tar)
{
if(ind==0)
if(tar+a[0]==0||tar-a[0]==0)
Return 1
Else
Retun 0
Plus=f(ind-1, a[ind]+tar)
Minus=f(ind-1, a[ind]-tar)
Return plus+minus
@@gauravpoharkar9797 For the recursion + Memoisation I think a better way would be to use a dictionary rather than the array because of the negative indexes specially in python since It will start indexing from the back.
Nice! Understood ❤.
Omg i made this problem for Coding ninjas
you baited me man kudos to u !
understood!!
What will be the base case for target as there target can be -1000 to 1000 so how he handles the negative values
UNDERSTOOOOOOD.
Pure genius 👌
understood!!😀😀😀
understood , outstanding explanation on this video !
Understood ❤
understood!
Revision done.
Was confused in the beginning: I had falsely assumed elements to be negative and thus took time to get to the point.
Nov'13, 2023 05:25 pm
Understood!!😇
Understood!
s1-s2=target , man striver is the guyyy!!!!
understood , you are the best teacher
Kudos to your intuition thanks striver
it becomes complicated when there are 0s in input arrays. because they can go to any of two subsets.
I think just returning 2 in case of 0 would work
Thank You
Understood!
Bro, this time understood the ""problem"" more clearly than solution :D. I read somewhere that understanding the problem well is like problem half solved. You are explaining same in multiple ways. I remember the same incidence from Codestudio contest from last week.
bhaiyaa aap hai naa aditya verma ka dekhiye acche se samjaya hai. mast hai.
@@ka.patelhimeyatulkumar19ba58 free me ad? Me Jo bola wo samajho pehle fir advice dena
understood :)❤
Understood!!
Understood, sir. Thank you very much.
Understoood
Understood Thanks you so much!
Superb yarrrrrrrr
Understood...Completed (21/56)
MindBlowingggggg
UNDERSTOOD
Understood !!!!!
Please make a vedio on binary lifting algorithm for kth ancestor in BT. Not much is available on RUclips.
Thanks in advance. 🙏🙏
genius !!!
understood very well❤❤❤
Wow it’s a tricky approach
awesome
why totsum-d should be even, incase of odd directly return false?
negative positive soln
f(idx, tar):
//base case:-
if(idx==0)
if(arr(idx)+tar == 0 || arr(idx)-tar == 0) return 1;
// logic and recursive call
int neg = f(idx-1, tar - (-arr(i)));
int pos = f(idx-1, tar - arr(i));
return neg+pos;
Time complexity: O(2^N) as every element has 2 options either positive or negative
understood
Understood, thanks!
Understood !!'
Understood :)
...
Striver bhaiya i was nnot able to comment in last vedio. I was saying that in DP-20 we can do further optimizations too as we have done in 0/1 knapsack by just using a single array reducing the SC to O(target+1)
Yes.
how?
I am gettig wrong answer by using only one array
Understood
int[] a = {1,2,3,1} target = 3
private static int getCount1(int[] a, int target, int length) {
if(target == 0){
return 1;
}
if(length == -1 ){
return 0;
}
int pos = getCount1(a, a[length]-target, length-1);
int neg = getCount1(a, -a[length]-target, length-1);
return neg + pos;
}
with this code I am able to solve the pblm
but if i try to apply memoization in this dp[arr.length][target+1]
then there is a pblm where target can go in negative. (-4, -1, -2....) so will get ArrayIndexOutOfBounds -4 for dp[length][target] .
any idea how to solve this kind of pblms
for such cases you need double the size of the arr
Striver bhaiya "Maximum profit in Job Scheduling" waala question explain kijiyegaa na and DP+Binary Search type waale questions explain kijiyegaa naa.
Thanks for DP series!!
great
this is also solution for the same
class Solution {
public:
int sol(vector& nums, int target,int ind,int curr)
{
if(ind==0)
{
if(target==curr && nums[0]==0)
return 2;
if(target==curr+nums[0] || target==curr-nums[0] )
return 1;
return 0;
}
int pos=sol(nums,target,ind-1,curr+nums[ind]);
int neg=sol(nums,target,ind-1,curr-nums[ind]);
return pos+neg;
}
int findTargetSumWays(vector& nums, int target) {
int n=nums.size();
// vector
return sol(nums,target,n-1,0);
}
};
thanks man! I was missing this return condition
@@aayushbisht4307 bruh what will be memorization matrix size
@@shivasai7707 May be memorization is not possible becoz curr will go to negative in some recursive calls
@@naveenramadheni2482 We can memoize it using unordered_map, instead of a 2d vector, use vector
@@GoldyAwad Bro that idea is really good bro. (now got it that how to memoize -ve indexes)
Understood, thanks
Hi..Can you tell that are there cases where memorization will give TLE but not tabulation?
In memoization we basicaaly use recussion to call function right,
So when we perform calls then we need to ressign variables for each call and calling each function takes a lot more time.
so memo o(n) >> tab o(n) Always
Just because of function calls it takes more time.
Target is negative here too. Run time error nhi dega?
terminate called after throwing an instance of 'std::length_error'
what(): cannot create std::vector larger than max_size()
I am gettting this error in leet code
Can anyone correct my solution:
int f(int i,int t,vector&arr){
if(i==0){
if(abs(t)==arr[0])return 1;
else return 0;
}
int neg=f(i-1,t+arr[i],arr);
int pos=f(i-1,t-arr[i],arr);
return neg+pos;
}
int targetSum(int n, int target, vector& arr) {
return f(n-1,target,arr);
}
it is going wrong when arr starts with 0.But I dont know y and how to rectify this.
Awesome observation
Understood!❤
plus + negative method of recursion is not working by my code, can anyone let me know the code of it
Eagerly waiting for the next video bro🙏
Big Brain...
can anyone pls help me? I am using the recursive approach , where I am either adding the current element to sum or subtracting the current element. and returning 1 when target == sum
this is the approach:-
int help(int n,int target,int sum ,vector&arr){
if(target == sum){
return 1;
}
if (n == 0){
return 0;
}
int ans = help(n-1,target,sum - arr[n - 1],arr);
ans += help(n - 1,target,sum + arr[n-1],arr);
return ans;
}
int targetSum(int n, int target, vector& arr) {
return help(n,target,0,arr);
}
thanks in advance for the help
target = abs(target) can be used to solve it using iterative dp.
Thanks for the suggestion
Hey Striver, In problem: L3. Longest Word With All Prefixes | Complete String | Trie in Trie Series, you gave c++ solution in java solution link. Can you please provide java solution?
amazing series
Before watching this video I was solving through + - method...It took hell lot of space to tabulate.......After watching video...I was shocked It was the same as S1-s2 = d ...
#UNDERSTOOD
I think it is not even possible to memoize or tabulate in that way because the range of target is not fixed due to possibility of negative integer, unless you take the max possible sum space on either sides. Please correct me if I am wrong.
@@vinayakgandhi5690 Yes I was taking range as max positive and max negative
@@vinayakgandhi5690 we can also use map instead of 2d matrix
UNDERSTOOD 😊