Target Sum

Examples

Input: nums = [1,1,1,1,1], target = 3
Output: 5

The five sign assignments that total 3 are: -1+1+1+1+1, +1-1+1+1+1, +1+1-1+1+1, +1+1+1-1+1, +1+1+1+1-1.

Input: nums = [1], target = 1
Output: 1

Only +1 works.

Constraints

• 1 <= nums.length <= 20

• 0 <= nums[i] <= 1000

• 0 <= sum(nums) <= 1000

• -1000 <= target <= 1000

Approach

Assigning signs is the same as splitting the numbers into a "positive group" (sum P) and a "negative group" (sum total - P, where total is the sum of all the numbers). Since the overall result must equal the target, P - (total - P) = target, which rearranges to P = (total + target) / 2.

That turns the problem into ordinary subset counting: how many subsets of nums add up to exactly P? Build a table where cell (i, s) means "using only the first i numbers, how many subsets sum to s?" Each number is either left out of the subset (carry forward the count from one fewer number) or included (add the count for the remaining sum, using one fewer number, since each number is used at most once).

If (total + target) is odd, or the target's absolute value exceeds the total, no split can possibly work, so the answer is immediately 0.

Solutions

Brute Force — Recursion

Try both a plus and a minus sign for every number, recursively, and count how many complete assignments land exactly on the target.

function findTargetSumWays(nums, target) {
  function solve(i, total) {
    if (i === nums.length) return total === target ? 1 : 0;
    return solve(i + 1, total + nums[i]) + solve(i + 1, total - nums[i]);
  }
  return solve(0, 0);
}

Time: O(2^n) · Space: O(n) — recursion depth

Optimal — Subset-Sum Counting with a 2D Table

Reduce sign assignment to counting subsets that sum to a specific target value P, then fill a standard subset-sum-count table indexed by (numbers considered, running sum).

function findTargetSumWays(nums, target) {
  const total = nums.reduce((sum, x) => sum + x, 0);
  if (Math.abs(target) > total || (total + target) % 2 !== 0) return 0;

  const subsetSum = (total + target) / 2;
  const n = nums.length;
  const table = Array.from({ length: n + 1 }, () => new Array(subsetSum + 1).fill(0));
  table[0][0] = 1;

  for (let i = 1; i <= n; i++) {
    for (let s = 0; s <= subsetSum; s++) {
      table[i][s] = table[i - 1][s]; // leave nums[i - 1] out of the subset
      if (s - nums[i - 1] >= 0) {
        table[i][s] += table[i - 1][s - nums[i - 1]]; // include nums[i - 1] in the subset
      }
    }
  }

  return table[n][subsetSum];
}

Time: O(n * (total + target)) · Space: O(n * (total + target))