For future readers, pls note the difference between this problem and knapsack 1. In Knapsack, there is no compulsion that each number should be included to achieve a sum 2. In Knapsack, there are positive numbers. Hence, for this problem : in the base case (target = 0 and empty/non-empty set), we cant blindly initialise it to 1.
i have a much simpler approach, suppose we divide the numbers in s1 and s2 sets. so s1+s2 = sum which we already know. s1-s2 is already given which is target difference. now add the two eqn and we get 2s1= sum+target. now all we need to do is find how many such s1 set exist, . thats the answer. this is basically subset sum problem.
Hi, big fan here. I solved this problem in a different way and it runs quite efficiently. I just use a dictionary (initialized with 1 zero so that the first number in the nums array has something to compare against) and iterate over the nums array, and then I use another dictionary to store all the ways the numbers in the dp dictionary, "n", can change given the number from the nums array, "new_dp[n+/-num]", while keeping track of how many ways that new number can be made "dp[n]". Then all you have to do is return dp[target] since it holds how many ways that number can be achieved. def findTargetSumWays(self, nums, target): dp = defaultdict(int) dp[0] = 1 for num in nums: new_dp = defaultdict(int) for n in dp: new_dp[n+num] += dp[n] new_dp[n-num] += dp[n] dp = new_dp return dp[target]
i tried both the ways, recursion-brute force and tis dp caching...for this array input, there is not much difference, bt when u increase the size of the array, you can see the DP magic in elapsed time..thank you
Hey there. Great solution but I wanted to know that will this solution be accepted in coding interviews or they might ask us to improve it to the bottom up/tabulation method. I understand those memoization solutions and am pretty comfortable with those and they also get accepted on leetcode. Please reply as I also want to crack those FAANG interviews just like you did. And thank you for all the efforts you put in those videos!
Hey does someone know if we can implement a tabulation solution to this problem? If not, how do we determine if a problem can or can't have tabulated solution??
A way to massively reduce the memory complexity (at a small price of 10 milliseconds more runtime) is for some reason using all the problem's parameters (plus the cache hashmap) as inputs to our helper function's parameters: class Solution: def findTargetSumWays(self, nums: List[int], target: int) -> int: cache = {} return self.dp(nums, 0, 0, target, cache) def dp(self, nums, index, sum, target, cache): if (index, sum) in cache: return cache[(index, sum)] if (index == len(nums)): if (sum == target): return 1 else: return 0
cache[(index, sum)] = self.dp(nums, index + 1, sum + nums[index], target, cache) + self.dp(nums, index + 1, sum - nums[index], target, cache) return cache[(index, sum)] Solution in video: 264 ms, 37.6 mb This solution: 274 ms, 17.4 mb
@@bhargavsangani2901 No idea, probably has to do with how LeetCode handles memory initialization, probably passing as parameters declares them "once"/less frequently VS the same batch of newly initialized memory each run of each test?
just a small question is the approach described here is actually a backtracking approach ? I saw the earlier n-queen problems and similar backtracking , we prune the path we tried for solution. If someone can help me clearing my doubt about this would be highly appreciated.
For those looking for a true DP solution with no recursion: class Solution: def findTargetSumWays(self, nums: List[int], target: int) -> int: total_sum = sum(nums) # Check if (target + total_sum) is odd, or target is out of bounds if (target + total_sum) % 2 != 0 or target > total_sum or target < -total_sum: return 0 # Calculate the subset sum we are looking for subset_sum = (target + total_sum) // 2 # DP array, dp[j] will store the number of ways to get sum j dp = [0] * (subset_sum + 1) dp[0] = 1 # There is 1 way to get sum 0 (by picking no elements) for num in nums: # Traverse backwards to avoid overwriting previous states for j in range(subset_sum, num - 1, -1): dp[j] += dp[j - num] return dp[subset_sum]
# The problem can be rephrased as finding two subsets of the array such that their difference equals the target sum. If you denote the sum of the positive subset as S1 and the sum of the negative subset as S2, you want: # S1-S2 = target # S1 + S2 = sum(nums) # S1 = (target + sum(nums))/2 # The problem then reduces to finding the number of ways to get a subset with sum S1. If (target + sum(nums)) is odd, there is no valid S1, so you return 0. Otherwise, you use a DP array to count the number of ways to achieve the sum S1.
Don't you think putting a bound check on '+' when total is higher than desired target will avoid unwanted branching ? Please do comment whenever you get time..
Found this bottom up solution on leetcode which is very efficient: res = {0:1} for num in nums: temp = {} for curSum in res: temp[curSum + num] = temp.get(curSum + num,0) + res[curSum] temp[curSum - num] = temp.get(curSum - num,0) + res[curSum] res = temp return res.get(target,0)
Tabulation code in java public int findTargetSumWays(int[] nums, int target) { int sum=0; for(int i:nums){ sum+=i; } if(Math.abs(target)>sum) return 0; //Let s1 and s2 be 2 subsets who's diff is target T and sum is S then //s1 +s2 =S //s1-s2 =T // 2*s1 = S+T //add both equations //2*s2 = S-T // subtract both //from above 2 equations its clear both shoud be even , as they are mutiple of 2 , //hence this condition if( (target+sum) %2!=0 || (sum-target)%2!=0) return 0; int reqSum=(-target+sum)/2; return subsetSum(nums,nums.length,reqSum); } int subsetSum(int a[], int n, int sum){ // Initializing the matrix int dp [] [] = new int [n][sum + 1] ; if(a[0]
Isn't this technically just DFS since there is no search pruning. We aren't discarding partial solutions early. That said, the definitions of backtracking often seem to largely overlap with DFS or made straight synonymous with DFS. Please correct me if my understanding is wrong.
can the time complexity be 2^n, cause each element in the array has 2 options, either to add it or subtract it. And can anyone explain how the the bottom-up approach is implemented. Couldn't understand the one in the solution.
for me I was able to come with recursive solution, no problem at all but not able to come with dp approach as was not able to find how the states would be saved and it does happen with me a lot. any idea on how to become better at this
Great video. Thank you for taking the time to make it. One quick question. I understand the solution other than what is happening at line 9. Why do we return dp[(i, total)]. I under stand that we have just checked if the tuple is in the dict as a key pair, but why do we return it? If you run the code without the line in leetcode it still passes, so I just want to understand. Thanks to anyone who can help!
dp is like a cache for storing previous results, inorder to avoid going through the entire computation again, we just return dp[(I, total)] that has already been previously computed
why is the time complexity O(m*n) and not O(m + n) since if there are two factors influencing the time complexity of a method we take the one with the highest complexity?
why do you need java solution? If you cannot write the solution in your programming language after watching the video, it means something else is wrong. Providing the solution in java will not help you. PS: I don't know python.
heres's mine i did... class Solution: def findTargetSumWays(self, arr: List[int], T: int) -> int: dp=[[0 for i in range(2*sum(arr)+1)] for _ in range(len(arr))] index_start=sum(arr) if Tindex_start: return 0 #iterate over possible solutions #Base Condition dp[0][index_start+arr[0]]=1 dp[0][index_start-arr[0]]+=1
for i in range(1,len(arr)): for j in range(-sum(arr),sum(arr)+1): if j-arr[i]>=-sum(arr): dp[i][index_start+j]+=dp[i-1][index_start+(j-arr[i])]
I do not understand dp[(i, total)] = backtrack(i+1, total+nums[i])+backtrack(i+1, total-nums[i]). How to store total number of solution? Could you or someone explain it to me?
Two recursive calls are made, one adds the current item, the other subtracts it. Each of these choices creates a new path to explore, but eventually when that path has been fully explored, it will return a value (if there is no way to use any of the numbers after i, that can make the current total == target, then it returns 0. But if there were one or more ways, it would return that value). Now imagine this has happened from the very bottom, all the way back to the top, and we're back to our very first call, that means every other node in the tree except the very first one has been evaluated, therefore we can just add the results of both choices.
def findTargetSumWays(self, nums: list[int], target: int) -> int: # the key is the current sum, the value is the number of possible expressions dp: dict[int, int] = {0: 1} for num in reversed(nums): dp_next: dict[int, int] = {} for cur_sum, count in dp.items(): dp_next[cur_sum + num] = dp_next.get(cur_sum + num, 0) + count dp_next[cur_sum - num] = dp_next.get(cur_sum - num, 0) + count dp = dp_next return dp.get(target, 0)
He returns dp[(i, total)], those '()' are important. In Python wrapping item(s) in brackets converts it to a tuple. This allows the index and total to be stored as a unique key within the hashmap
Basically, you start with the index at 0 and the total argument at 0. You are accumulating the result as you go from index to index. If you see the base case, the if condition checks when index i == len(nums) which means we have processed all the elements in the array, then we check if the total == target; if we achieve this, we return 1, otherwise, we didn't succeed and thus return 0. So start the call with backtrack (index=0, total=0), and total accumulates to be equal to target if the path is successful. Hope this helps.
i have a much simpler approach, suppose we divide the numbers in s1 and s2 sets. so s1+s2 = sum which we already know. s1-s2 is already given which is target difference. now add the two eqn and we get 2s1= sum+target. now all we need to do is find how many such s1 set exist, . thats the answer. this is basically subset sum problem.
For future readers, pls note the difference between this problem and knapsack
1. In Knapsack, there is no compulsion that each number should be included to achieve a sum
2. In Knapsack, there are positive numbers. Hence, for this problem : in the base case (target = 0 and empty/non-empty set), we cant blindly initialise it to 1.
good point
Very good point. Thanks!
This is exactly the problem I was working on and hoping for a video. You are a saint, Neetcode.
Same😭
six months ago I saw this video, and now i'm back to learn this solution again : (
Did you get it ?)
No problem, we all forget solutions
+1
i have a much simpler approach, suppose we divide the numbers in s1 and s2 sets. so s1+s2 = sum which we already know. s1-s2 is already given which is target difference. now add the two eqn and we get 2s1= sum+target. now all we need to do is find how many such s1 set exist, . thats the answer. this is basically subset sum problem.
I had forgotten the coin change solution, dp isn't very intuitive.
I never realized how powerful decision trees are until I saw your videos.
Thank you my prophet.
💀
Hi, big fan here. I solved this problem in a different way and it runs quite efficiently. I just use a dictionary (initialized with 1 zero so that the first number in the nums array has something to compare against) and iterate over the nums array, and then I use another dictionary to store all the ways the numbers in the dp dictionary, "n", can change given the number from the nums array, "new_dp[n+/-num]", while keeping track of how many ways that new number can be made "dp[n]". Then all you have to do is return dp[target] since it holds how many ways that number can be achieved.
def findTargetSumWays(self, nums, target):
dp = defaultdict(int)
dp[0] = 1
for num in nums:
new_dp = defaultdict(int)
for n in dp:
new_dp[n+num] += dp[n]
new_dp[n-num] += dp[n]
dp = new_dp
return dp[target]
This is really an excellent answer.
🗿
my solution using the bottom up approach:
class Solution:
def findTargetSumWays(self, nums: List[int], target: int) -> int:
dp = {}
dp[0] = 1
for n in nums:
newdp = {}
for key in dp:
if (key + n) in newdp:
newdp[key + n] += dp[key]
else:
newdp[key + n] = dp[key]
if (key - n) in newdp:
newdp[key - n] += dp[key]
else:
newdp[key - n] = dp[key]
dp = newdp
return dp.get(target, 0)
i tried both the ways, recursion-brute force and tis dp caching...for this array input, there is not much difference, bt when u increase the size of the array, you can see the DP magic in elapsed time..thank you
I'll be applying to faang companies on jan-feb; it was a blessing finding ur channel. Thanks bud :")
Did you get it?
@@gametech7046I kinda stalked his Linkedin, apparenty not.
Did you make it?
Hey there. Great solution but I wanted to know that will this solution be accepted in coding interviews or they might ask us to improve it to the bottom up/tabulation method. I understand those memoization solutions and am pretty comfortable with those and they also get accepted on leetcode. Please reply as I also want to crack those FAANG interviews just like you did. And thank you for all the efforts you put in those videos!
Generally they look for tabular method because it is harder
To clarify, the dp pair is storing the number of ways starting at index i to sum to the given original total with total already in hand
Hey does someone know if we can implement a tabulation solution to this problem? If not, how do we determine if a problem can or can't have tabulated solution??
U a God. Finally been waiting for this video!
I got the hang of recursive DFS thanks to your videos with crystal clear explanations :0
Thanks a lot!!!
hi. can you provide me the link ?
@@jesuschrist8590
ruclips.net/video/pfiQ_PS1g8E/видео.html&ab_channel=NeetCode
A way to massively reduce the memory complexity (at a small price of 10 milliseconds more runtime) is for some reason using all the problem's parameters (plus the cache hashmap) as inputs to our helper function's parameters:
class Solution:
def findTargetSumWays(self, nums: List[int], target: int) -> int:
cache = {}
return self.dp(nums, 0, 0, target, cache)
def dp(self, nums, index, sum, target, cache):
if (index, sum) in cache:
return cache[(index, sum)]
if (index == len(nums)):
if (sum == target):
return 1
else:
return 0
cache[(index, sum)] = self.dp(nums, index + 1, sum + nums[index], target, cache) + self.dp(nums, index + 1, sum - nums[index], target, cache)
return cache[(index, sum)]
Solution in video: 264 ms, 37.6 mb
This solution: 274 ms, 17.4 mb
Tried this, this is freaking huge reduction in memory footprint 🤯. Why though?
@@bhargavsangani2901 No idea, probably has to do with how LeetCode handles memory initialization, probably passing as parameters declares them "once"/less frequently VS the same batch of newly initialized memory each run of each test?
Backtracking works since nums size
just a small question is the approach described here is actually a backtracking approach ? I saw the earlier n-queen problems and similar backtracking , we prune the path we tried for solution.
If someone can help me clearing my doubt about this would be highly appreciated.
For those looking for a true DP solution with no recursion:
class Solution:
def findTargetSumWays(self, nums: List[int], target: int) -> int:
total_sum = sum(nums)
# Check if (target + total_sum) is odd, or target is out of bounds
if (target + total_sum) % 2 != 0 or target > total_sum or target < -total_sum:
return 0
# Calculate the subset sum we are looking for
subset_sum = (target + total_sum) // 2
# DP array, dp[j] will store the number of ways to get sum j
dp = [0] * (subset_sum + 1)
dp[0] = 1 # There is 1 way to get sum 0 (by picking no elements)
for num in nums:
# Traverse backwards to avoid overwriting previous states
for j in range(subset_sum, num - 1, -1):
dp[j] += dp[j - num]
return dp[subset_sum]
# The problem can be rephrased as finding two subsets of the array such that their difference equals the target sum. If you denote the sum of the positive subset as S1 and the sum of the negative subset as S2, you want:
# S1-S2 = target
# S1 + S2 = sum(nums)
# S1 = (target + sum(nums))/2
# The problem then reduces to finding the number of ways to get a subset with sum S1. If (target + sum(nums)) is odd, there is no valid S1, so you return 0. Otherwise, you use a DP array to count the number of ways to achieve the sum S1.
@@pabloj1336 Thanks for explaining your solution 😄
Don't you think putting a bound check on '+' when total is higher than desired target will avoid unwanted branching ?
Please do comment whenever you get time..
NeedCode must know this, just maybe share with others. Compared with caching, Bottom-Up approach can reduce the space complexity to O(sum(nums)).
f(x, curr_sum) = {
1, if x == len(nums) and curr_sum == target,
0, if x == len(nums) and curr_sum != target,
f(x + 1, curr_sum + nums[x]) + f(x + 1, curr_sum - nums[x]), otherwise
}
Found this bottom up solution on leetcode which is very efficient:
res = {0:1}
for num in nums:
temp = {}
for curSum in res:
temp[curSum + num] = temp.get(curSum + num,0) + res[curSum]
temp[curSum - num] = temp.get(curSum - num,0) + res[curSum]
res = temp
return res.get(target,0)
man i just went to solve this this morning and you posted this yesterday. nice man
also have u thought of making a meme channel called yeet code
such concise explanantion! Thank you so much !
Tabulation code in java
public int findTargetSumWays(int[] nums, int target) {
int sum=0;
for(int i:nums){
sum+=i;
}
if(Math.abs(target)>sum) return 0;
//Let s1 and s2 be 2 subsets who's diff is target T and sum is S then
//s1 +s2 =S
//s1-s2 =T
// 2*s1 = S+T //add both equations
//2*s2 = S-T // subtract both
//from above 2 equations its clear both shoud be even , as they are mutiple of 2 ,
//hence this condition
if( (target+sum) %2!=0 || (sum-target)%2!=0) return 0;
int reqSum=(-target+sum)/2;
return subsetSum(nums,nums.length,reqSum);
}
int subsetSum(int a[], int n, int sum){
// Initializing the matrix
int dp [] [] = new int [n][sum + 1] ;
if(a[0]
Isn't this technically just DFS since there is no search pruning. We aren't discarding partial solutions early. That said, the definitions of backtracking often seem to largely overlap with DFS or made straight synonymous with DFS. Please correct me if my understanding is wrong.
I think you're right. It's a straightforward DFS with caching
This was confused me as well
do you prefer using top down approach?
everyone at first talking about market. Sad reality but
can the time complexity be 2^n, cause each element in the array has 2 options, either to add it or subtract it. And can anyone explain how the the bottom-up approach is implemented. Couldn't understand the one in the solution.
for me I was able to come with recursive solution, no problem at all but not able to come with dp approach as was not able to find how the states would be saved and it does happen with me a lot.
any idea on how to become better at this
I believe it can be solved with 1D DP array as well.
Very nice explanation
Is it possible to do this using a bottom up approach like you do with alot of other DP problems?
And if not can you explain why you use one over the other in certain situations
I did it!
Great video. Thank you for taking the time to make it. One quick question. I understand the solution other than what is happening at line 9. Why do we return dp[(i, total)]. I under stand that we have just checked if the tuple is in the dict as a key pair, but why do we return it? If you run the code without the line in leetcode it still passes, so I just want to understand.
Thanks to anyone who can help!
dp is like a cache for storing previous results, inorder to avoid going through the entire computation again, we just return dp[(I, total)] that has already been previously computed
What's the time complexity of this solution?
why is the time complexity O(m*n) and not O(m + n) since if there are two factors influencing the time complexity of a method we take the one with the highest complexity?
I really liked your videos. Can you provide us the Java solutions as well.
why do you need java solution? If you cannot write the solution in your programming language after watching the video, it means something else is wrong. Providing the solution in java will not help you.
PS: I don't know python.
Very clean and easy explanation . Thanks a lot
What does the tabulation DP solution look like?
heres's mine i did...
class Solution:
def findTargetSumWays(self, arr: List[int], T: int) -> int:
dp=[[0 for i in range(2*sum(arr)+1)] for _ in range(len(arr))]
index_start=sum(arr)
if Tindex_start:
return 0
#iterate over possible solutions
#Base Condition
dp[0][index_start+arr[0]]=1
dp[0][index_start-arr[0]]+=1
for i in range(1,len(arr)):
for j in range(-sum(arr),sum(arr)+1):
if j-arr[i]>=-sum(arr):
dp[i][index_start+j]+=dp[i-1][index_start+(j-arr[i])]
if j+arr[i]
Hello sir, I'm a beginner to ur channel. Plz let me know what is the right way or right approch to see coding question
What is line number 11 and 12 doing?
I think im starting to get this a little bit
super helpful
I do not understand dp[(i, total)] = backtrack(i+1, total+nums[i])+backtrack(i+1, total-nums[i]). How to store total number of solution? Could you or someone explain it to me?
Two recursive calls are made, one adds the current item, the other subtracts it. Each of these choices creates a new path to explore, but eventually when that path has been fully explored, it will return a value (if there is no way to use any of the numbers after i, that can make the current total == target, then it returns 0. But if there were one or more ways, it would return that value). Now imagine this has happened from the very bottom, all the way back to the top, and we're back to our very first call, that means every other node in the tree except the very first one has been evaluated, therefore we can just add the results of both choices.
@@avenged7ex This explained it perfectly, thanks.
GOOD VIDEO
Can you share the solution for "688. Knight Probability in Chessboard " using dp
Thanks a lot
no tabulation for this problem?
I understand these videos but when it is time to solve on my own, I won't get the intuition at all.
Anybody else in the same boat as me?
Can it be solved using bottom up DP? Why? Why not?
it can be see leetcode official solution
def findTargetSumWays(self, nums: list[int], target: int) -> int:
# the key is the current sum, the value is the number of possible expressions
dp: dict[int, int] = {0: 1}
for num in reversed(nums):
dp_next: dict[int, int] = {}
for cur_sum, count in dp.items():
dp_next[cur_sum + num] = dp_next.get(cur_sum + num, 0) + count
dp_next[cur_sum - num] = dp_next.get(cur_sum - num, 0) + count
dp = dp_next
return dp.get(target, 0)
Is there a 2d array solution for this
Is this backtracking? I would’ve thought this is just dfs
i dont use python, why are you returning dp[I,total] ?
He returns dp[(i, total)], those '()' are important. In Python wrapping item(s) in brackets converts it to a tuple. This allows the index and total to be stored as a unique key within the hashmap
why did you call backtrack(0,0 ) should it not be backtrack(0,target)??
Basically, you start with the index at 0 and the total argument at 0. You are accumulating the result as you go from index to index. If you see the base case, the if condition checks when index i == len(nums) which means we have processed all the elements in the array, then we check if the total == target; if we achieve this, we return 1, otherwise, we didn't succeed and thus return 0. So start the call with backtrack (index=0, total=0), and total accumulates to be equal to target if the path is successful.
Hope this helps.
i have a much simpler approach, suppose we divide the numbers in s1 and s2 sets. so s1+s2 = sum which we already know. s1-s2 is already given which is target difference. now add the two eqn and we get 2s1= sum+target. now all we need to do is find how many such s1 set exist, . thats the answer. this is basically subset sum problem.
It would be nice to explore the bottom up dp solution for this too.
2400. Number of ways to reach a point after exactly k steps . Can u help with this with proper explanation.
that is not dp solution? its just recursion + mem
Can't see any relation between your code and the explanation provided earlier. They look completely unrelated.
anyone with solution in cpp or datatype to be used in cpp for dictionary?????
hash map
c++ code plz
```
class Solution {
public:
map m ;
vector nums ;
int n;
int target ;
int backtrack(int index ,int total){
if(index == n){
return total == target ? 1 :0;
}
auto findcomb= m.find({index,total});
if(findcomb!=m.end()){
return findcomb->second ;
}
return m[{index,total}] =
backtrack(index+1,total+nums[index])
+backtrack(index+1 ,total-nums[index]);
}
int findTargetSumWays(vector& nums1, int target1) {
nums = nums1;
target = target1 ;
n = nums.size();
return backtrack(0 ,0);
}
};
```
translate it yourself