Target Sum
Target Sum: assign a + or - to each number in nums so the resulting expression equals target. Return how many assignments achieve it.
- 1 <= nums.length <= 20
- 0 <= nums[i] <= 1000
- 0 <= sum(nums[i]) <= 1000
- -1000 <= target <= 1000
Intuition
Target sum counts the ways to assign + or - to each number so the expression equals a target. With n numbers there are 2ⁿ assignments, so enumeration is hopeless for large inputs.
The transformation that solves it treats the assignment as a partition. Let P be the numbers given + and N those given -. Then:
P − N = target and P + N = totalSum
Adding those gives 2P = target + totalSum, so:
- P = (target + totalSum) / 2, which turns the problem into counting subsets that sum to that value — ordinary subset-sum.
That reduction is the whole insight, and it converts an exponential search into a pseudo-polynomial DP.
Two checks must come first. If target + totalSum is odd, no valid split exists and the answer is 0, since P must be a whole number. And if abs(target) exceeds totalSum, the target is unreachable.
The DP counts subsets rather than testing reachability, so dp[s] holds how many subsets sum to s, seeded with dp[0] = 1 — exactly one way to reach zero, by choosing nothing.
The transition is dp[s] += dp[s − num], swept downward for each number so no number is used twice.
Zeros in the input deserve attention: each zero can take either sign without changing the sum, doubling the count. The subset-sum formulation handles this automatically, which is one reason it is preferable to ad-hoc counting.
The cost is O(n × P) time and O(P) space.
Assigning ± signs is a disguised subset-sum. If the positives sum to P, the negatives sum to total - P, and P - (total - P) = target gives P = (total + target) / 2. Counting sign assignments becomes counting subsets with sum P — a knapsack over counts rather than booleans.
Approach
Before reading on: price up what the direct approach costs here, then ask what a single cell should mean, and which earlier cells it needs. Aim for O(n x (sum + target)/2) time and O((sum + target)/2) space.
Reframe as a partition
Numbers given + form set P and those given - form N, with P − N = target and P + N = total. Two equations, two unknowns.
Derive the subset target
Adding the equations gives P = (target + total) / 2, turning the problem into counting subsets that sum to that value.
Reject impossible inputs
If target + total is odd, return 0 — P must be a whole number. Likewise if abs(target) exceeds the total.
Count subsets, not reachability
dp[s] holds how many subsets sum to s, seeded with dp[0] = 1 — one way to reach zero, by choosing nothing.
Sweep the sums downward
Apply dp[s] += dp[s - num] from high to low for each number, so no number is counted twice in the same subset.
Let zeros resolve themselves
Each zero can take either sign, doubling the count. The subset-sum formulation handles this automatically without special cases.
Cost of the tabulation
Each number sweeps the target range, giving O(n × P) time and O(P) space — pseudo-polynomial in the derived subset sum.
Solution & live demo
Common pitfalls
Not rejecting a non-integer or negative P
P = (total + target) // 2
if (total + target) % 2 or total + target < 0:
return 0
P = (total + target) // 2If total + target is odd, no subset can have that sum and the floor division fabricates a nearby target that yields a wrong non-zero count. A negative value would size the array wrongly or throw.
Using boolean reachability
if dp[t - x]: dp[t] = True
dp[t] += dp[t - x]
The question asks how many sign assignments work, not whether one does. Accumulating counts propagates the number of distinct subsets reaching each sum.
Iterating the inner loop ascending
for t in range(x, P + 1):
for t in range(P, x - 1, -1):
Same 0/1 knapsack rule as subset-sum: each number carries exactly one sign and may be used once. Ascending lets a number contribute to its own count, massively overcounting.
Edge cases
P would be fractional, so no assignment exists. Return 0 before allocating the table.
Even making every number positive or every one negative cannot reach the target. Return 0.
Each zero can take either sign without changing the value, so it doubles the count. The DP handles this correctly — dp[t] += dp[t - 0] doubles every entry, which is exactly right, whereas a naive subset enumeration that treats subsets as sets would undercount.
Handled by the formula, since (sum + target) remains valid as long as it is non-negative and even. No separate branch is needed.