Target Sum
Problem
+ or a - sign in front of every number of
nums (keeping their order) to form an expression. Count how many different sign
assignments make the expression evaluate to exactly target.[1,1,1,1,1], target=3Output5[1], target=1Output11 ≤ n ≤ 20 · 0 ≤ nums[i] ≤ 1000 · sum(nums) ≤ 1000 · |target| ≤ 1000
Try it yourself
class Solution {
public int findTargetSumWays(int[] nums, int target) {
}
}
P = numbers with +, N = with
-. Then P - N = target and P + N = total, so
P = (total + target) / 2. Just count subsets summing to P.Instinct Choose items to hit or stay under a target sum (can it be done, best value, fewest items, how many ways) - index a DP array by the remaining capacity.
Memory hack Once? Walk back. Many? Walk forward. Each item used at most once loops capacity downward; reusable items loop it upward.
Open the Knapsack DP guide →Approaches
Brute ForceTry Every Sign (Recursion)
O(2n)Space O(n)At index i branch twice: add nums[i] or subtract
it. At the end, count 1 if the running sum equals target. Explores all
2n sign patterns.
public int findTargetSumWays(int[] nums, int target) { return count(nums, 0, 0, target); } private int count(int[] nums, int i, int sum, int target) { if (i == nums.length) return sum == target ? 1 : 0; return count(nums, i + 1, sum + nums[i], target) + count(nums, i + 1, sum - nums[i], target); }
Fine for n = 20 (~106 leaves), but doesn't scale.
BetterMemoization on (index, running sum)
O(n·T)Space O(n·T)The running sum always lies in [-total, total], so shift it by
total and memoize (i, sum) in a 2-D table with
T = 2·total + 1 columns. Each state is solved once.
public int findTargetSumWays(int[] nums, int target) { int total = 0; for (int x : nums) total += x; Integer[][] memo = new Integer[nums.length][2 * total + 1]; return count(nums, 0, 0, target, total, memo); } private int count(int[] nums, int i, int sum, int target, int total, Integer[][] memo) { if (i == nums.length) return sum == target ? 1 : 0; if (memo[i][sum + total] != null) return memo[i][sum + total]; int ways = count(nums, i + 1, sum + nums[i], target, total, memo) + count(nums, i + 1, sum - nums[i], target, total, memo); return memo[i][sum + total] = ways; }
Polynomial, but a 2-D table and recursion overhead.
OptimalSubset-Count Knapsack (1-D)
O(n·P)Space O(P)After the algebra, dp[s] = number of subsets (so far) summing to
s; each number adds dp[s - num] to dp[s],
looping s downwards (0/1 use). If total + target is odd or
|target| > total, no assignment exists.
public int findTargetSumWays(int[] nums, int target) { int total = 0; for (int x : nums) total += x; if (Math.abs(target) > total || (total + target) % 2 != 0) return 0; int p = (total + target) / 2; int[] dp = new int[p + 1]; dp[0] = 1; // empty subset for (int num : nums) { for (int s = p; s >= num; s--) { dp[s] += dp[s - num]; } } return dp[p]; }
Dry run[1,1,1,1,1], target=3 → P = (5+3)/2 = 4; cells = dp[0..4]
- init10000pempty subset
- 1st 111000pdp[1] += dp[0]
- 2nd 112100pPascal row 2
- 3rd 113310pPascal row 3
- 4th 114641pPascal row 4
- 5th 11510105pdp[4] = 5 ✔
Smallest table (P ≤ total), no recursion — optimal.
dp[s] += dp[s] doubles the count, since
+0 and -0 are distinct assignments.At a glance
| Level | Approach | Time | Space |
|---|---|---|---|
| Brute Force | Try Every Sign (Recursion) | O(2n) | O(n) |
| Better | Memoization on (index, running sum) | O(n·T) | O(n·T) |
| Optimal | Subset-Count Knapsack (1-D) | O(n·P) | O(P) |
- Negative
target: check|target| > total, nottarget > total. - Forgetting the parity check —
(total+target)/2rounds and overcounts. - Memo indexed by raw sum — negative index; shift by
total.
- Start with the 2n recursion (n ≤ 20 makes it acceptable), then memoize.
- Derive
P = (total + target)/2on the whiteboard — it's the key step. - Point out it's the counting twin of Partition Equal Subset Sum.