Count of Subsets with a Given Sum

The problem

Implement `countOfSubsetWithGivenSum(nums, target)`: given an array of non-negative integers, return how many distinct subsets sum to exactly `target`. Each number may be used at most once, and subsets are distinguished by position, not value.

`nums = [2, 3, 5, 6, 8, 10], target = 10` returns `3` — `{10}`, `{2, 8}` and `{2, 3, 5}`. `nums = [1, 1, 1], target = 2` returns `3`, not `1`: the three `1`s are different elements even though they look identical, so each pair counts separately.

The approach

Structurally this is `subsetSumProblem` with one substitution. `memo[i][j]` stops meaning 'can the first `i` numbers reach `j`' and starts meaning 'how many ways can they'. The item loop, the capacity loop and the `nums[i-1] <= j` guard are all byte-for-byte the same; only the cell type and the combining operator move.

`skip || take` becomes `skip + take` because the two branches partition the solution space. Every subset that sums to `j` either contains `nums[i-1]` or doesn't — never both, never neither — so the subsets counted by `memo[i-1][j]` and those counted by `memo[i-1][j - nums[i-1]]` are disjoint sets with no overlap to subtract. Addition is exactly right here; it would be wrong the moment an element could be reused, because then the same multiset would be reachable through two paths.

The base cases translate along with the type. `memo[0][j] = 0` — an empty prefix has zero ways to reach a positive sum, which is `false` restated. `memo[i][0] = 1` — every prefix has exactly one way to reach `0`, by taking nothing, which is `true` restated. `memo[0][0]` gets written twice again and the column loop wins again, landing on `1`: there is exactly one empty subset and it sums to zero.

The caveat this formulation hides is zeros in the input. Forcing `memo[i][0] = 1` down the entire column asserts 'one way to make zero' for every prefix, but if `nums` contains a `0`, that element can be in or out of the subset without changing the sum, so a prefix with `k` zeros has `2^k` ways. `[0, 0, 1]` with `target = 1` should be `4` and this returns `1`. Seeding only `memo[0][0] = 1` and letting the recurrence fill the rest of the column fixes it — the `+` doubles at each zero on its own.

The solution

export 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 * target)Space O(n * target)