Coin Change — Count the Number of Ways

The problem

Implement `coinChangeMaixmumNoOfWays(coins, sum)`: given coin denominations available in unlimited supply, count the distinct combinations that add up to `sum`. Order doesn't matter — `1 + 2` and `2 + 1` are the same combination.

`coins = [1, 2, 5], sum = 5` returns `4`: `5`, `2+2+1`, `2+1+1+1`, `1+1+1+1+1`. `coins = [2], sum = 3` returns `0`. Note that the function name says 'maximum' but the thing being computed is a count — the name is wrong and so is the spelling of it.

The approach

Two edits to the unbounded knapsack turn optimisation into counting. `values` is gone from the signature because there's nothing to maximise, and `Math.max(include, exclude)` becomes `include + exclude` because both branches are now counts of disjoint sets of solutions rather than competing candidates. Every way to make `j` either uses coin `i` at least once or never uses it at all — no combination is in both buckets, so adding is exact rather than an approximation.

The zero column flips to `1` and that's the load-bearing base case. `memo[i][0] = 1` asserts there is exactly one way to make sum `0` — take nothing. Leaving it at `0` makes every path that bottoms out at an exact sum contribute nothing, and the whole table returns `0` for every input. Row `0` stays `0`: with no coins at all, a positive sum has zero ways. The two overlap at `memo[0][0]`, the column loop runs second, `1` wins, and that's the correct claim — the empty multiset sums to zero.

The include branch reads `memo[i][j - weights[i-1]]`, same row, which is the unbounded part: after spending one coin `i` you may spend another. The exclude branch reads `memo[i-1][j]`, previous row, which is what forbids revisiting a coin you've already decided to abandon. That ordering — coins in the outer loop, sums in the inner — is exactly what makes `1+2` and `2+1` collapse into one count, because coin `2` is only ever considered after coin `1` has been fully resolved.

Flip those two loops and the problem changes underneath you. The 1D version iterated sum-outer, coin-inner counts *permutations* and answers Combination Sum IV instead; the same recurrence, the same array, a different number. The 2D form here can't accidentally do that — the row index makes the coin ordering structural rather than a property of loop nesting — which is a decent argument for writing the table out in full before collapsing it.

The naming is worth a second: `coinChangeMaixmumNoOfWays` has a typo in it and describes an objective the function doesn't have, and the helper is `unboundedKanpsack` in three separate files. Neither breaks anything, but a mistyped name propagates by copy-paste — this is the third file that inherited the same transposed `Kanpsack`.

The solution

export function coinChangeMaixmumNoOfWays(coins, sum) {
  return unboundedKanpsack(coins, sum);
}

function unboundedKanpsack(weights, capacity) {
  const memo = Array.from({ length: weights.length + 1 }, () =>
    Array(capacity + 1).fill(null),
  );

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

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

  // return the maximum value
  return memo[weights.length][capacity];
}

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