Target Sum

The problem

Implement `targetSum(nums, target)`: given an array of non-negative integers, put a `+` or a `-` in front of each one, concatenate them into an expression, and return how many of the `2^n` sign assignments evaluate to `target`.

`nums = [1, 1, 1, 1, 1], target = 3` returns `5` — flip exactly one sign to minus and the other four to plus, and there are five ways to choose which one. `target = 7` returns `0`; the whole array only sums to `5`.

The approach

Signs are just a partition in disguise. Call `S1` the numbers that get a `+` and `S2` the ones that get a `-`. The expression evaluates to `sum(S1) - sum(S2)`, so asking for it to equal `target` is asking for a subset difference of `target` — which is exactly the input `countOfSubsetWithGivenDiff` takes. Every sign assignment corresponds to exactly one pair `(S1, S2)` and vice versa, so counting one counts the other; nothing is lost or double-counted in the translation.

Which means the derivation from the last entry carries over unchanged: `sum(S1) - sum(S2) = target` and `sum(S1) + sum(S2) = totalSum` add to `2 * sum(S1) = totalSum + target`, so `sum(S1) = (totalSum + target) / 2`. It eventually boils down to the same problem solved last — count the subsets hitting a fixed sum — and the body of the function is one arithmetic line plus a call.

The parity guard is the same one, for the same reason: `totalSum + target` odd means `sum(S1)` would be a fraction, and no assignment of integers produces a fractional sum, so the answer is `0` rather than a broken table. What's new is `Math.abs(target) > totalSum`, and it's not cosmetic. A `target` more negative than `-totalSum` makes `(totalSum + target) / 2` negative, and `Array(negative + 1)` throws a `RangeError` instead of returning `0`. Guarding the magnitude turns a crash into the correct answer.

One caveat this version inherits and doesn't fix: zeros. LeetCode's constraints allow `nums[i] === 0`, and a `0` can take either sign without changing the total, so each one doubles the answer. Forcing `memo[i][0] = 1` down the whole first column says 'exactly one way to make zero — take nothing', which stops being true the moment a zero exists. `[0, 0, 1], target = 1` should be `4` and this returns `1`. The fix is to seed only `memo[0][0] = 1` and let the recurrence fill the rest of the column, which naturally doubles at every zero.

The solution

export function targetSum(nums, target) {
  const totalSum = nums.reduce((acc, curr) => acc + curr, 0);
  if (Math.abs(target) > totalSum) return 0;
  if ((totalSum + target) % 2 !== 0) return 0;
  const newTarget = (totalSum + target) / 2;
  return countOfSubsetWithGivenSum(nums, newTarget);
}

function countOfSubsetWithGivenSum(nums, target) {
  const memo = Array.from({ length: nums.length + 1 }, () =>
    Array(target + 1).fill(null),
  );

  // initialize the first row with 0
  for (let j = 0; j <= target; j++) {
    memo[0][j] = 0;
  }

  // initialize the first column with 1
  for (let i = 0; i <= nums.length; i++) {
    memo[i][0] = 1;
  }

  // fill the memo table
  for (let i = 1; i <= nums.length; i++) {
    for (let j = 1; j <= target; j++) {
      if (nums[i - 1] <= j) {
        memo[i][j] = memo[i - 1][j] + memo[i - 1][j - nums[i - 1]];
      } else {
        memo[i][j] = memo[i - 1][j];
      }
    }
  }

  // return the result
  return memo[nums.length][target];
}

Time O(n * sum)Space O(n * sum)