Assign + or − to every number so that the expression evaluates to target. Return the number of ways.
Before you code
If P is the sum of the numbers given +, then P − (total − P) = target, so P = (total + target) / 2. The question becomes: how many subsets sum to P?
Hints
- If total + target is odd or negative, or |target| > total, the answer is 0.
- Count subsets with
dp[s] += dp[s - x], looping s downward, starting fromdp[0] = 1. - Zeros double the count, which this recurrence handles naturally.
Production & complexity notes
When solving Target sum on LeetCode (medium), always state your loop or recursion invariant before writing code. Verify how your chosen data structure behaves on degenerate inputs (single-element inputs, all-duplicate keys, strictly monotonic sequences, or maximum constraint sizes up to $10^5$ elements). In production interviews, pair your implementation with an explicit time and auxiliary space complexity proof, explain why alternative brute-force approaches violate the latency budget, and trace how cache locality and memory allocation overhead affect wall-clock throughput on real hardware. Review the step-by-step memory trace in Knapsack and subsets to reinforce the underlying pattern.
What it practices
Recognizing a knapsack in disguise, from Knapsack and subsets.