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