#494 Target Sum
the problem
In plain words
Write a '+' or a '−' in front of every number in nums and add everything up. Out of all 2ⁿ sign choices, count the ones whose total equals target.
in nums = [1,1,1,1,1], target = 3
out 5
Make exactly one of the five 1s negative: 5 choices.
in nums = [1], target = 1
out 1
- 1 ≤ nums.length ≤ 20
- 0 ≤ nums[i] ≤ 1000
- 0 ≤ sum(nums) ≤ 1000
- −1000 ≤ target ≤ 1000
your turn
Try it before you peek
Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.
Solve it in the browser
LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.
Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.
Marking the problem solved, or opening every hint, also shows it.
the aha
Key insight
pattern0/1 knapsack
The '+' numbers form a group P and the '−' numbers a group N. P − N = target and P + N = total, so P = (total + target) / 2. Counting sign choices is counting subsets with that sum — 0/1 knapsack counting.
solutions
From brute force to optimal
ways(i, sum) = ways(i + 1, sum + nums[i]) + ways(i + 1, sum − nums[i]).
- i == n → 1 if sum == target, else 0.
- Add the two branches.
Two signs per number: about 10⁶ leaves for n = 20 — slow but it passes.
Recursion depth n.
class Solution { public int findTargetSumWays(int[] nums, int target) { return ways(nums, 0, 0, target); } /** Sign patterns for nums[i..] that turn the running sum `sum` into target. */ private int ways(int[] nums, int i, int sum, int target) { if (i == nums.length) return sum == target ? 1 : 0; return ways(nums, i + 1, sum + nums[i], target) // put '+' before nums[i] + ways(nums, i + 1, sum - nums[i], target); // or '-' }}The running sum lives in [−total, total]; store it at index sum + total.
- int[n][2·total + 1] memo filled with −1.
- Check, compute, store.
n × (2·total + 1) states, O(1) each.
The memo.
class Solution { public int findTargetSumWays(int[] nums, int target) { int total = 0; for (int x : nums) total += x; // The running sum lives in [-total, total]: shift it by +total to get an array index. int[][] memo = new int[nums.length][2 * total + 1]; for (int[] row : memo) Arrays.fill(row, -1); // -1 = unknown (counts are never negative) return ways(nums, 0, 0, target, total, memo); } private int ways(int[] nums, int i, int sum, int target, int total, int[][] memo) { if (i == nums.length) return sum == target ? 1 : 0; if (memo[i][sum + total] != -1) return memo[i][sum + total]; int count = ways(nums, i + 1, sum + nums[i], target, total, memo) + ways(nums, i + 1, sum - nums[i], target, total, memo); return memo[i][sum + total] = count; }}Turn signs into one subset, then count subsets with a 1D row swept downward.
- |target| > total or (total + target) odd → 0.
- P = (total + target) / 2; ways[0] = 1.
- For each x: for s = P down to x: ways[s] += ways[s − x].
- Return ways[P].
n numbers × P + 1 sums, P ≤ 1000.
One row of counts.
class Solution { public int findTargetSumWays(int[] nums, int target) { int total = 0; for (int x : nums) total += x; // plus - minus = target and plus + minus = total, so plus = (total + target) / 2 if (Math.abs(target) > total || (total + target) % 2 != 0) return 0; int want = (total + target) / 2; // the '+' numbers must add up to exactly this int[] ways = new int[want + 1]; // ways[s]: subsets of the numbers seen so far with sum s ways[0] = 1; // the empty subset for (int x : nums) { for (int s = want; s >= x; s--) { // DOWNWARD: each number joins a subset at most once ways[s] += ways[s - x]; // subsets without x, plus subsets that add x } } return ways[want]; }}From signs to a subset count
in the room
How to say it in the interview
talk track
- "Brute force is fine for n = 20 — about a million leaves — but let me do better."
- Do the algebra out loud: P − N = target, P + N = total → P = (total + target) / 2.
- Guards first (|target| ≤ total, even total + target), then count subsets with sum P, sums looping downward.
traps
- Missing the parity check: (total + target) / 2 silently rounds down and counts the wrong thing.
- Zeros: a 0 can take either sign, so it doubles the count. The loop must run down to s = x (that is, to s = 0 for a zero).
- Negative running sums used directly as array indices in a memo: shift them by +total.
what they ask next
Follow-ups
Last Stone Weight II (LC 1049)?
The same split into two groups; find the reachable subset sum closest to total / 2.
List the expressions themselves?
Backtracking over the signs — the output alone can have up to 2ⁿ lines.
before you submit
Edge cases to test
- |target| > total → 0.
- total + target odd → 0.
- Zeros: [0,0,0] with target 0 → 8 (each zero can be + or −).
- Negative target: [2,3] with target −1 → 1 (+2 −3).
practise next
Similar problems
- #416Partition Equal Subset SumMediumin Dynamic Programming
- #518Coin Change IIMediumin Dynamic Programming
- #78SubsetsMediumin Backtracking