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.
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); }
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.
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 😊
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.💌💌💌💌
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); }
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); } };
I've alternate solution for this, just instead of take/nottake, do +, - #include int solve(int ind, int target, vector& arr){ if(ind==0){ if(arr[0]==target || arr[0]==-target) return 1; else return 0; } int pos=solve(ind-1, target-arr[ind], arr); int neg=solve(ind-1, target+arr[ind], arr); int var=pos+neg; return var; } int targetSum(int n, int target, vector& arr) { // Write your code here. return solve(n-1, target, arr); }
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)
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!
@@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.
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.
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
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.
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
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!!
below is the solution for the problem here we either assign negative or positive to a number so the target can become negative so we use map to store negative indices. int solution(int n,int target,vector&arr,map&dp) { if(n==0) { if(target==0&&arr[0]==0) return 2; if(arr[0]+target==0) return 1; if(arr[0]-target==0) return 1; return 0; } if(dp.find({n,target})!=dp.end()) return dp[{n,target}]; int pos=solution(n-1,target-arr[n],arr,dp); int neg=solution(n-1,target+arr[n],arr,dp); return dp[{n,target}]=pos+neg; } int findTargetSumWays(vector& nums, int target) { map dp; int n=nums.size(); return solution(n-1,target,nums,dp); } if any doubt you can ask in comment.
solved the problem using recursive approach , just added extra parameter p to maintain the path sum i.e., p+arr[i] and p-arr[i]. and in base condition just check if p is equal to target or not; class Solution { public int findTargetSumWays(int[] arr, int target) { int n = arr.length,k=target; int p=0; return find(n-1,k,p,arr); } int find(int n,int k,int p,int[] arr){ if(n==-1) return (k==p)?1:0; int left= 0,right=0; right = find(n-1,k,p+arr[n],arr); left = find(n-1,k,p-arr[n],arr); return left+right; } }
i solved it using +,- approach where i biased the -ve sm with some extra space, defintely a overengineered solution, if only i had realized the pattern of previous question 🥲
