Count of Subsets with a Given Difference

The problem

Implement `countOfSubsetWithGivenDiff(nums, diff)`: given an array of non-negative integers, count the ways to split it into two subsets `S1` and `S2` such that `sum(S1) - sum(S2) === diff`. Every element goes into exactly one subset.

`nums = [1, 1, 2, 3], diff = 1` returns `3` — `{1,3}/{1,2}`, `{1,3}/{1,2}` with the other `1`, and `{1,1,2}/{3}` all leave a gap of one. `nums = [1, 2, 3], diff = 2` returns `0`; the total is `6`, and `(6 + 2) / 2 = 4` is unreachable from those three numbers.

The approach

Write down what's known and the reduction falls out. `sum(S1) - sum(S2) = diff` and `sum(S1) + sum(S2) = totalSum`. Add the two and the `sum(S2)` terms cancel: `2 * sum(S1) = totalSum + diff`, so `sum(S1) = (totalSum + diff) / 2`. That number is fully determined by the input — no search involved — and once `S1` is chosen, `S2` is whatever's left, so counting valid `S1` sets counts valid splits exactly once each.

The parity guard is a correctness statement, not a micro-optimisation. `totalSum` and `diff` must have the same parity for `(totalSum + diff) / 2` to be an integer, and a subset of integers can only sum to an integer. If they disagree, there is genuinely no split — returning `0` before the table exists is the right answer, and it also keeps `Array(target + 1)` from being handed a fraction, which would allocate a nonsense length and quietly miss on every lookup.

After that there's nothing new to write: `countOfSubsetWithGivenSum(nums, target)` is the entire body. This is the third problem in a row where the real work is the two lines in front of the call, which is the point — 'count subsets with difference `diff`' and 'count subsets with sum `k`' are the same question asked from opposite ends, and the table doesn't care which end you started from.

The gap worth naming: unlike `targetSum`, this version doesn't guard `diff > totalSum`. A `diff` larger than the total gives a `target` bigger than any reachable sum — the table still returns `0`, correctly, just after allocating columns that were never going to be `true`. A negative `diff` below `-totalSum` is worse: `target` goes negative and `Array(target + 1)` throws. Worth an `if (Math.abs(diff) > totalSum) return 0;` alongside the parity check.

The solution

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

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 * (totalSum + diff) / 2)Space O(n * (totalSum + diff) / 2)