· By John Kavanagh

Coin Change II: Count Combinations Without Counting Their Order

Hands arrange stacks of gold-coloured coins on a white table.
Image by Towfiqu barbhuiya, licensed from Unsplash.

If I make four from a one and a three, have I found one answer or two? For Coin Change II, changing their order doesn't produce a new answer. For an ordered counting problem, it would. The arithmetic is identical; the definition of an answer is doing the work.

That distinction shows up in the order of two loops. Swap them and the program can still look entirely respectable, pass a few examples, and count something the caller didn't request.

The Coin Change II problem on LeetCode gives us distinct positive denominations, an unlimited supply of each, and a target amount. We return the number of combinations that make that amount. This differs from finding the fewest coins, which I cover in my original Coin Change walkthrough.


Describe a Combination Without Arranging It

For denominations 1, 3, 4 and amount six, the combinations are six ones; one three with three ones; two threes; and one four with two ones. There are four answers.

Each answer can be described by how many coins of each denomination it contains. That description has no ordering ambiguity. For example, the combination containing one three and three ones corresponds to counts 3, 1, 0, regardless of how the coins are laid on the table.

A direct recursive reference can choose the quantity of the first denomination, then the quantity of the second, and so on. That approach avoids permutations naturally, but it repeats many smaller remainder problems. The table will retain their counts instead.

The state needs two ideas: the amount we're making and which denominations we're allowed to use. Omitting the second idea from the explanation is where loop‑order instructions start to sound like magic.


One Denomination at a Time

Let ways[s] mean the number of combinations making subtotal s using only denominations processed so far. Before processing any denomination, there is one way to make zero: choose no coins. Every positive subtotal has zero ways.

When processing coin value c, combinations making s either use no copies of that coin or use at least one. The first group is already in ways[s]. For the second group, remove one copy of c; what remains is a combination making s - c using the old denominations and possibly this denomination again.

That final clause determines the inner loop direction. We scan subtotals upwards, so ways[s - c] already includes combinations using the current denomination. Adding one more copy is allowed because the supply is unlimited.

The outer coin loop ensures that each combination is introduced in one denomination stage. We never separately construct the same bag by choosing a different order of coins. The counting follows a fixed order of denomination types, even if the input array itself isn't sorted.


Watch the Table Build Six

Using denominations 1, 3, 4, the count table develops as follows:

Denominations available0123456
None1000000
11111111
1, 31112223
1, 3, 41112334

During the three‑coin pass, the update at subtotal six reads the newly updated subtotal three. That adds both three‑plus‑three and three‑plus‑three‑ones to the existing six‑ones combination.

During the four‑coin pass, subtotal six reads subtotal two, adding the combination consisting of a four and two ones. The result is four, matching the explicit quantity descriptions.

If we put the subtotal loop outside, we instead ask which coin comes last in each sequence. For 1, 2 and amount three, that counts 1,1,1, 1,2, and 2,1: three sequences rather than two combinations. It's a useful algorithm, just an unhelpful answer to this question.


Keep Intermediate Counts Exact

LeetCode guarantees that the final answer fits a signed 32‑bit integer. I still use bigint for the table, because that promise concerns the requested amount, not every smaller subtotal we happen to calculate.

For example, an odd amount with only even denominations is unreachable. Its answer is zero, whilst reachable even subtotals may have very large counts. A guarantee about the final zero doesn't bound those other cells.

The ECMAScript specification's safe‑integer limit explains why sufficiently large integer counts cannot all be represented exactly as number. Using bigint keeps the recurrence literal and makes the numeric argument simple. We convert only the final result, whose problem‑specific bound makes that conversion exact.

This requires an ES2020‑or‑later TypeScript target and a runtime supporting BigInt. The TypeScript target documentation explains how the target controls emitted language features. Compiling for an older target isn't a substitute for supplying runtime support.


The Complete Solution

const change = (amount: number, coins: number[]): number => {
  const ways: bigint[] = Array(amount + 1).fill(0n);
  ways[0] = 1n;

  for (const coin of coins) {
    for (let subtotal = coin; subtotal <= amount; subtotal += 1) {
      ways[subtotal] += ways[subtotal - coin];
    }
  }

  return Number(ways[amount]);
};

There are O(coins.length × (amount + 1)) table operations and O(amount + 1) stored counts. With arbitrary‑precision integers, addition and storage also depend on the counts' bit lengths; those bounds describe table work and cells, not constant‑cost arithmetic on unbounded integers.

The function doesn't mutate or sort the denominations. Their uniqueness matters: processing the same denomination twice would treat it as two distinct types and overcount. Positive values also matter. A zero‑valued coin would permit infinitely many quantities without changing the amount, which is a different problem rather than an awkward array index.

For amount zero, the function returns one. There is one empty combination, not zero combinations. This base case is what allows the first usable coin to create its own subtotal during an ordinary update.


Tests That Distinguish the Nearby Problems

I would test an unreachable amount, an amount matching one denomination, amount zero, and multiple uses of a single coin. Those cases check the empty combination and the unlimited supply independently.

Then I'd use 1, 2 at amount three to catch ordered counting. Reversing the denomination array should preserve the result, and a denomination larger than the amount should have no effect. Those properties are useful because they follow from combinations, rather than from a particular implementation order.

For an independent reference, enumerate denomination quantities recursively and count the assignments whose weighted total matches the amount. Bound each quantity by the remaining amount divided by its coin value. Comparing this reference with every non‑empty denomination subset of a small range provides broad coverage without importing another copy of the same table recurrence.

I'd also retain an unreachable odd target with many even denominations. It exercises the reason for exact intermediate storage, although a correct final zero alone doesn't prove that every internal cell remained exact. Numeric design still needs an argument alongside tests.


Keep the State Attached to the Loops

My guide to dynamic‑programming state returns to this habit: write down what a cell means at a particular point in the iteration. Here it counts combinations using the denomination types already introduced.

The coin‑first loop prevents different arrangements of the same bag from becoming new answers. The ascending subtotal loop permits repeated use of the current coin. Both choices follow from that state meaning, which is considerably more useful than remembering a loop pattern and hoping it belongs to the right problem.


Want to find out more?

If you need senior hands‑on support with a complex React or Next.js platform, migration, performance issue, or technical SEO problem, send me the context and I'll tell you where I can help.