Target Sum - Dynamic Programming - Leetcode 494 - Python

0:00 - Read the problem
2:17 - Drawing Explanation
7:53 - Coding Explanation

leetcode 494

#facebook #interview #python
Disclosure: Some of the links above may be affiliate links, from which I may earn a small commission.

[mudd]

This is exactly the problem I was working on and hoping for a video. You are a saint, Neetcode.

[abhishekpawar]

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.

[yizhang]

I never realized how powerful decision trees are until I saw your videos.
Thank you my prophet.

[liairi]

six months ago I saw this video, and now i'm back to learn this solution again : (

[Ibby]

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]

[sathyanarayanankulasekaran]

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

[dc]

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)

[gametech]

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!

[benalfred]

I'll be applying to faang companies on jan-feb; it was a blessing finding ur channel. Thanks bud :")

[greyreynyn]

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

[nhbknhb]

I got the hang of recursive DFS thanks to your videos with crystal clear explanations :0

Thanks a lot!!!

[piercef]

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.

[pabloj]

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]

[mehekswe]

do you prefer using top down approach?

[vgsuresh]

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.

[edwardteach]

U a God. Finally been waiting for this video!

[sanskartiwari]

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??

[dheepthaaanand]

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

[ywl.]

Backtracking works since nums size <= 20; DP would be better for this kind of problem. Start with 2D then can be optimized to 1D.

[anjaliyadav]

such concise explanantion! Thank you so much !