Target Sum
Count the ways to put + and − in front of each number to reach a target, by turning it into counting subsets with sum (total + target) / 2.
Problem Understanding
Target Sum: put a + or − in front of every number in nums, then add them all. Return how many sign choices give exactly target.
Example: nums = [1, 1, 1, 1, 1], target = 3 returns 5: one of the five 1s gets a minus sign.
Attempt 1: Try Every Sign
Each number has two signs, so there are 2^n combinations. A DFS over (index, running sum) is correct, and memoising it helps, but the running sum can be negative and the state space is awkward. A little algebra removes the signs entirely.
The Intuition: Signs Are Just a Subset
Split the numbers into the plus group P and the minus group N:
P − N = targetP + N = total
Adding them: P = (total + target) / 2. So a sign choice is nothing more than a subset whose sum is (total + target) / 2. If that is not a whole number, or |target| > total, the answer is 0.
Counting subsets with a given sum is the counting version of Partition Equal Subset Sum: dp[j] is the number of subsets that add up to j, dp[0] = 1, and for each number dp[j] += dp[j − num] for j going down, so each number is used once.
Interactive Walkthrough
The numbers are on top, with the one being added marked. Below, dp[j] counts the subsets that make j, up to the plus group's sum. The sweep runs right to left: j reads dp[j − num], which is shaded.
Dry Run Table
Input: nums = [1, 1, 1, 1, 1], target = 3. total = 5, so the plus group sums to (5 + 3) / 2 = 4.
| After number | dp[0] | dp[1] | dp[2] | dp[3] | dp[4] |
|---|---|---|---|---|---|
| (start) | 1 | 0 | 0 | 0 | 0 |
| 1st 1 | 1 | 1 | 0 | 0 | 0 |
| 2nd 1 | 1 | 2 | 1 | 0 | 0 |
| 3rd 1 | 1 | 3 | 3 | 1 | 0 |
| 4th 1 | 1 | 4 | 6 | 4 | 1 |
| 5th 1 | 1 | 5 | 10 | 10 | 5 |
Five ways: choose which four 1s are positive.
The Solution Template
Reduce to counting subsets with sum (total + target) / 2, then a 1D 0/1 knapsack.
Target Sum Code
1var findTargetSumWays = function(nums, target) {2 const total = nums.reduce((a, b) => a + b, 0);3 if (Math.abs(target) > total || (total + target) % 2) return 0;4 const goal = (total + target) / 2;5 const dp = new Array(goal + 1).fill(0);6 dp[0] = 1;7 for (const num of nums) {8 for (let j = goal; j >= num; j--) {9 dp[j] += dp[j - num];10 }11 }12 return dp[goal];13};
Edge Cases & Common Mistakes
- |target| > total: return 0 before computing a negative or oversized goal.
- Odd total + target: no subset can sum to a half; return 0.
- Negative target: the formula still works, as long as |target| ≤ total.
- Zeros: each 0 doubles the count; make sure the inner loop includes
j = num = 0. - Sweeping upward: that reuses a number within one pass and overcounts.
Summary
A sign choice is a subset P with P − N = target and P + N = total, so P sums to (total + target) / 2. Rule out impossible targets, then count subsets with that sum using dp[j] += dp[j − num] with j descending. O(n · sum) time, O(sum) space.
More practice: DSA interview questions with answers · patterns cheat sheet