Minimum Subset Sum Difference

The problem

Implement `minimumSubsetDiff(nums)`: split an array of non-negative integers into two subsets and return the smallest possible value of `|sum(S1) - sum(S2)|`. Every element must land in exactly one subset.

`[1, 6, 11, 5]` returns `1` — `{1, 5, 6}` sums to `12` and `{11}` to `11`. `[1, 2, 7]` returns `4` — the best split is `{1, 2}` against `{7}`. When a perfect halving exists the answer is `0`, which makes `equalSumPartitionProblem` a yes/no query on this same result.

The approach

The reachable set is the whole point. If a subset sums to `s`, the complement sums to `totalSum - s` by construction, so the difference is `|totalSum - 2s|` — a function of `s` alone. Minimising it means finding the reachable `s` closest to `totalSum / 2`, and since every `s` above the midpoint mirrors one below it, scanning `j` from `0` to `Math.floor(totalSum / 2)` covers every distinct difference without checking anything twice.

That's why the helper returns the whole `memo` instead of a single boolean. Every earlier problem in this series asked one question of the table and read one cell; here the question is 'what's the best reachable sum', which is a scan of the final row. The table has always contained that information — `memo[n][j]` is 'is `j` reachable using all `n` numbers' for every `j` at once — and this is the first problem that spends it.

The scan collects into `possibleValuesOfSum` and then takes the last element, which works because `j` ascends, so the last one pushed is the largest. It can never be empty: `memo[i][0] = true` for every prefix, so `j = 0` is always reachable, and in the degenerate case of an all-zero or empty array the answer comes out `totalSum - 0 = totalSum`, which is right. A running `let best = 0` would do the same job in `O(1)` space instead of building an array only to read its tail.

One naming nit worth fixing before this gets copy-pasted: the local helper is called `countOfSubsetWithGivenSum` but it's the *boolean* subset-sum table — it fills `false`/`true`, uses `||`, and the two comments still say 'initialize with 0' and 'initialize with 1' from whatever it was pasted from. It behaves correctly; it just claims to be the counting variant from the entry above, and `true`/`false` happening to be truthy in `if (memo[nums.length][j])` is what hides the mismatch.

The solution

export function minimumSubsetDiff(nums) {
  const totalSum = nums.reduce((acc, curr) => acc + curr, 0);
  const memo = countOfSubsetWithGivenSum(nums, totalSum);
  const possibleValuesOfSum = [];
  for (let j = 0; j <= Math.floor(totalSum / 2); j++) {
    if (memo[nums.length][j]) {
      possibleValuesOfSum.push(j);
    }
  }
  return totalSum - 2 * possibleValuesOfSum[possibleValuesOfSum.length - 1];
}

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] = false;
  }

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

  // 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;
}

Time O(n * totalSum)Space O(n * totalSum)