Target Sum

The problem. Given an integer array nums and an integer target, put a + or a - in front of every number. Count how many of these expressions add up to target.

Example

nums = [1, 1, 1, 1, 1], target = 3  ->  5
nums = [1], target = 1               ->  1
nums = [1, 2, 3], target = 7         ->  0    (the most you can reach is 6)
nums = [0, 1], target = 1            ->  2    (+0 +1 and -0 +1 both count)

The idea: from signs to a subset

Brute force tries both signs for each number: 2ⁿ expressions. Better: let P be the sum of the numbers that get + and N the sum of those that get -. Then P - N = target and P + N = total. Adding the two equations gives `P = (total + target) / 2`. So every valid expression is just a subset that sums to P — the same 0/1 knapsack as Partition Equal Subset Sum, except now we count subsets instead of asking whether one exists. If total + target is odd or |target| > total, no expression works.

1. Plain recursion: + or -

1function findTargetSumWays(nums, target) {2  const count = (i, sum) => {                    // ways to finish, given the sum so far3    if (i === nums.length) return sum === target ? 1 : 0;4    return count(i + 1, sum + nums[i]) + count(i + 1, sum - nums[i]);   // + or -5  };6  return count(0, 0);7}

Time O(2ⁿ), space O(n). Fine for LeetCode's n ≤ 20 (about a million calls), but it repeats work: many different sign choices reach the same (i, sum).

2. Memoize (i, sum)

1function findTargetSumWays(nums, target) {2  const memo = new Map();                        // "i,sum" -> ways3  const count = (i, sum) => {4    if (i === nums.length) return sum === target ? 1 : 0;5    const key = i + "," + sum;6    if (!memo.has(key)) memo.set(key, count(i + 1, sum + nums[i]) + count(i + 1, sum - nums[i]));7    return memo.get(key);8  };9  return count(0, 0);10}

Time O(n · total), space O(n · total). The running sum can be anything from -total to total, so there are n × (2 · total + 1) states. Java and C++ shift the sum by total to use it as an array index.

3. Count subsets that sum to P

1function findTargetSumWays(nums, target) {2  const total = nums.reduce((a, b) => a + b, 0);3  if (Math.abs(target) > total || (total + target) % 2 !== 0) return 0;   // no split works4  const plus = (total + target) / 2;             // the + numbers must sum to this5  const ways = new Array(plus + 1).fill(0);      // ways[s]: subsets so far that sum to s6  ways[0] = 1;                                   // the empty subset7  for (const x of nums) {8    for (let s = plus; s >= x; s--) ways[s] += ways[s - x];   // backwards: x is used once9  }10  return ways[plus];11}

Time O(n · P), space O(P). Zeros need no special case: for x = 0 the loop runs ways[s] += ways[s], doubling every count — exactly right, since +0 and -0 are two different expressions.

Comparing the approaches

Edge cases to test

Variations