Target Sum
Problem Statement
You are given an integer array nums and an integer target. Assign either a plus sign or a minus sign to every number, then concatenate the signed numbers into an expression. Return the number of different sign assignments that evaluate to target.
Input
An integer array nums and an integer target.
Output
An integer: the number of sign assignments whose expression value equals target.
Constraints
- •
1 <= nums.length <= 20 - •
0 <= nums[i] <= 1000 - •
0 <= sum(nums[i]) <= 1000 - •
-1000 <= target <= 1000
Examples
Example 1
nums = [1,1,1,1,1], target = 3
5Example 2
nums = [1], target = 1
1Example 3
nums = [0,0,0,0,0,0,0,0,1], target = 1
256Learning Objectives
- Derive the algebra that turns signed choices into a subset-sum count.
- Use 1D counting DP where each number is processed exactly once.
- Explain why descending iteration is still required even though the DP stores counts instead of booleans.
- Handle impossible parity and out-of-range target cases before tabulation.
Intuition
A direct recursion chooses plus or minus for each number. That is a binary tree, but many branches only differ by which subset of numbers ended up positive.
Let P be the sum of numbers assigned plus, and N be the sum of numbers assigned minus. The expression value is P - N = target. The total sum is P + N = total. Add the equations and you get 2P = total + target, so P = (total + target) / 2.
Now the problem is no longer about signs. It asks how many subsets have sum (total + target) / 2. Each number can be assigned once, so this is a 0/1 knapsack count. The capacity loop goes downward for the same reason as Partition Equal Subset Sum: a number cannot be counted twice in one sign assignment.
Common mistakes
- ×Forgetting to reject cases where **abs(target) > total**.
- ×Forgetting that **total + target** must be even for the subset target to be an integer.
- ×Scanning sums ascending, which lets one number contribute multiple times to a single assignment.
- ×Mishandling zeroes; a zero doubles the count for every reachable sum because plus zero and minus zero are distinct assignments.
State Definition
Let dp[s] be the number of ways to choose a subset from the numbers processed so far whose sum is exactly s. After the algebraic transformation, the answer is dp[subset], where subset = (total + target) / 2.
State Transition
For each number num, every existing subset count can either skip num or take num. Taking it contributes all ways that previously made s - num.
The recurrence is dp[s] = dp[s] + dp[s - num] for s from subset down to num.
Base case: dp[0] = 1, the empty subset. Descending iteration keeps the update 0/1. When num = 0, the loop still runs once for every sum and doubles dp[s], correctly representing plus zero and minus zero.
Solutions
Solution: 1D 0/1 subset count
Convert the sign equation into a subset target, then count subsets with that sum. This avoids exponential sign recursion while preserving the fact that each array element is used once.
Step-by-step
- Sum all numbers.
- If target is outside [-total, total], return 0.
- If total + target is odd, return 0 because no integer subset sum exists.
- Initialise dp[0] = 1 and process each number.
- Scan sums descending and add dp[s - num] into dp[s].
- Return dp[subset].
O(n · subset)
O(subset)
The transformed target is at most the total sum of nums.
Java implementation
Dry Run
Sample input
nums = [1, 1, 1, 1, 1], target = 3. Here total = 5, so subset = (5 + 3) / 2 = 4.
| number processed | sum scan | dp[0..4] after processing | meaning |
|---|---|---|---|
| first 1 | 4 down to 1 | [1, 1, 0, 0, 0] | One way to make sum 1. |
| second 1 | 4 down to 1 | [1, 2, 1, 0, 0] | Two choices make sum 1; one choice makes sum 2. |
| third 1 | 4 down to 1 | [1, 3, 3, 1, 0] | Counts match choosing k ones from three. |
| fourth 1 | 4 down to 1 | [1, 4, 6, 4, 1] | There is one way to choose all four processed ones. |
| fifth 1 | 4 down to 1 | [1, 5, 10, 10, 5] | There are 5 subsets of sum 4, so there are 5 target expressions. |
The target expression count equals the number of subsets with positive sum 4. That final value is dp[4] = 5.
Complexity Analysis
The expensive sign tree collapses into a pseudo-polynomial subset count over the total sum. The correctness hinges on the algebra and on descending 0/1 iteration.
1D 0/1 subset count
O(n · subset)
O(subset)
The transformed target is at most the total sum of nums.
Interview Tips
Derive P = (total + target) / 2 out loud. That algebra is the interview signal that you are not just memorising a DP table. Then call out the zero case and the descending loop; both are common sources of wrong accepted-looking solutions.
Likely follow-ups
- Return one valid sign assignment instead of only the count.
- What if each number could be assigned plus, minus, or unused?
- How would you solve it if the total sum were too large for pseudo-polynomial DP?
- How does the answer change when all numbers are positive and distinct?
Similar Problems
Key Takeaways
- Signed target problems can often be transformed into subset-sum equations.
- For Target Sum, count subsets with sum **(total + target) / 2**.
- Counting DP still needs descending capacity iteration when each item is 0/1.
- Zero values double counts because plus zero and minus zero are different assignments.