Target Sum
Assign a + or - to each number in nums so the resulting expression equals target. Return how many assignments achieve it.
Intuition
Trying all 2^n sign assignments is the obvious brute force. The reframe: let P be the sum of the numbers given a plus and N the sum of those given a minus. Then P - N = target and P + N = sum, so adding them gives P = (sum + target) / 2. Counting sign assignments is therefore identical to counting subsets that sum to P — the same knapsack as Partition Equal Subset Sum, except we count subsets instead of merely detecting one.
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
Turn the sign problem into a subset problem
Every assignment partitions the numbers into a positive group and a negative group. Writing P for the positive group's sum and N for the negative group's, the expression evaluates to P - N and the two groups together account for the whole array, so P + N = sum(nums). Solving the pair gives P = (sum + target) / 2. Each valid assignment corresponds to exactly one subset with that sum, and vice versa — so the counts are equal.
Reject the impossible cases from the formula
P must be a non-negative integer. If sum + target is odd, no assignment can work — the answer is 0. Likewise if sum + target is negative, or equivalently abs(target) > sum. Both checks are O(n) and must come before the DP; skipping them produces a negative or fractional table size.
Count subsets with a 1-D knapsack
Let dp[t] be the number of subsets summing to t, initialised with dp[0] = 1 (the empty subset). For each number, sweep t downward from P and do dp[t] += dp[t - x]. The downward direction enforces one use per element, exactly as in the boolean version — the only change is accumulating counts rather than OR-ing booleans. The answer is dp[P].
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.