Target Sum gives an array of non-negative integers and a target, and asks how many ways you can put a plus or minus sign before each number so the total equals the target. The interview value is in the reduction from signs to subset sum.
Each number has two choices, so recursion explores 2^n assignments. Memoising on (index, running sum) cuts it to O(n * S) where S is the sum of the array. That is already acceptable, and saying it first shows you can reach a working answer quickly.
Split the numbers into P (plus) and N (minus). Then sum(P) - sum(N) = target and sum(P) + sum(N) = total. Adding the two gives sum(P) = (target + total) / 2. So the question becomes: how many subsets sum to that value? If target + total is odd or abs(target) > total, the answer is 0.
def find_target_sum_ways(nums, target):
total = sum(nums)
if abs(target) > total or (target + total) % 2:
return 0
goal = (target + total) // 2
dp = [0] * (goal + 1)
dp[0] = 1
for x in nums:
for s in range(goal, x - 1, -1):
dp[s] += dp[s - x]
return dp[goal]
Time is O(n * goal) and space is O(goal). Iterating s downwards is what makes each number usable at most once; going upwards would turn it into unbounded knapsack and overcount.
A zero can take either sign without changing the sum, so it doubles the count. The dp above handles that automatically, because dp[s] += dp[s - 0] doubles every entry. It is a good edge case to mention before the interviewer does.
Partition Equal Subset Sum is the boolean version with target 0, Last Stone Weight II is the minimisation version, and Coin Change II is the unbounded counting cousin.
Give the memoised recursion, then derive the subset-sum target on the whiteboard in two lines, then explain the loop direction. Disclosure: I am on the team behind Linkjob AI, which gives real-time hints on reductions like this one.
Further reading: Linkjob AI resource directory