Counting the ways to make change

You have coins of n different values c1, …, cn and as many coins of each value as you like. In how many different ways can you pay an amount A exactly? With coins 1, 2 and 5 and amount 5 there are four ways:

5        2+2+1        2+1+1+1        1+1+1+1+1

Here 2+2+1 and 1+2+2 are the same way, because they use the same coins: only how many coins of each value you use matters (a multiset of coins, also called a combination), not the order you hand them over. Later we will see how to count ordered sequences instead.

This is a counting problem, not an optimization problem. The Making Change page asks for the fewest coins that make an amount, and takes a minimum over the choices. Here we add up the choices, because every choice leads to different ways.

The idea in plain words

Listing every way is hopeless for large amounts, because there are far too many (coins 1, 2, 5, 10, 20, 50, 100 and 200 can make 200 in 73,682 ways). Instead we count, and we split the question into smaller questions of the same kind. Line the coin values up in some order and bring them in one at a time. Suppose we already know how many ways there are to make every amount using only the first i − 1 coin values, and now coin ci is allowed too. Every way to make a either

  • never uses coin ci: then it is one of the ways we already counted with the first i − 1 coins; or
  • uses it at least once: take one copy of ci out, and what is left is a way to make a − ci that may still use coin ci (and the earlier coins).

No way is in both groups, and every way is in one of them, so the count is the sum of the two groups' counts.

The four ways to make 5 from coins 1, 2, 5 split in two groups: three ways never use coin 5 (2+2+1, 2+1+1+1, 1+1+1+1+1), counted with coins 1 and 2 only; one way uses coin 5, and taking that 5 out leaves amount 0, the empty way
Every way either skips the new coin or uses it; removing one copy of the coin turns the second group into ways for a smaller amount.

The recurrence

Let ways[i][a] be the number of ways to make amount a using only the first i coin values (row i of the table, labelled "≤ i" in the animation). Then

ways[0][0] = 1                                   (the empty way)
ways[0][a] = 0                  for a > 0        (no coins, no way)
ways[i][a] = ways[i-1][a]                        don't use coin i   (cell above)
           + ways[i][a - c_i]   if c_i ≤ a      use coin i again   (c_i cells to the left)
Table of ways for coins 1, 2, 5 and amounts 0 to 5; the cell ways[3][5] = 4 is the cell above it, 3 (ways without coin 5), plus the cell 5 to the left in its own row, ways[3][0] = 1 (ways using coin 5 again)
Each cell adds the ways that skip the new coin (cell above) and the ways that use it once more (c_i cells to the left in the same row).

Why is ways[0][0] 1 and not 0? Choosing no coins at all is a perfectly good way to pay 0. It is also where every real way ends up: take the coins of a way out one by one and you reach amount 0 with nothing left. If ways[0][0] were 0, every cell would be 0.

Note that the "use coin i" term stays in the same row i. That is what lets a coin be used again and again. In 0/1 knapsack, where each item is used at most once, the same term looks one row up instead.

The algorithm step by step

  1. Make a table with rows 0, 1, …, n (coins allowed so far) and columns 0, 1, …, A (amounts).
  2. Fill row 0: a 1 in column 0 and 0 everywhere else.
  3. For each row i = 1, …, n, from left to right: copy the value from the cell above, and if ci ≤ a add the value ci cells to the left in the row being filled. That cell is already filled, because it is further left.
  4. The answer is the bottom-right cell ways[n][A].
CountWays(c[1..n], A):
    for a = 0 to A:
        ways[0][a] = 0
    ways[0][0] = 1
    for i = 1 to n:                       // coins in the outer loop
        for a = 0 to A:
            ways[i][a] = ways[i-1][a]
            if c[i] ≤ a:
                ways[i][a] = ways[i][a] + ways[i][a - c[i]]
    return ways[n][A]

In the animation the cell being filled is outlined in red, the "don't use coin i" source (the cell above) is blue, the "use coin i" source is green, and the coin of the current row is yellow in the coin list. At the end the answer cell is orange and, when there are at most 12 ways, the ways themselves are listed under the table.

A worked example: coins 1, 2, 5 and amount 5

Enter 1,2,5 and 5 above and press Count Ways to watch exactly these steps.

  • Row "none". ways[0] = 1 0 0 0 0 0: only amount 0 can be made, by the empty way.
  • Row ≤ 1 (coin 1). For a = 0 coin 1 is too big, so copy the 1 from above. For a = 1: above 0, plus ways[1][0] = 1, gives 1 (the way "1"). For a = 2: 0 + ways[1][1] = 0 + 1 = 1 (the way "1+1"), and the same for 3, 4, 5. Row: 1 1 1 1 1 1. With only 1-coins there is exactly one way to make each amount.
  • Row ≤ 2 (coin 2). a = 0, 1: coin 2 is too big, copy 1 and 1. a = 2: 1 + ways[2][0] = 1 + 1 = 2 (1+1 and 2). a = 3: 1 + ways[2][1] = 1 + 1 = 2 (1+1+1 and 2+1). a = 4: 1 + ways[2][2] = 1 + 2 = 3 (1+1+1+1, 2+1+1, 2+2). a = 5: 1 + ways[2][3] = 1 + 2 = 3. Row: 1 1 2 2 3 3.
  • Row ≤ 3 (coin 5). For a = 0, …, 4 coin 5 is too big, so the row copies 1 1 2 2 3. a = 5: 3 (the ways without a 5) + ways[3][0] = 1 (the way "5" itself) = 4.
amount a      0   1   2   3   4   5
none          1   0   0   0   0   0
≤ 1 (coin 1)  1   1   1   1   1   1
≤ 2 (coin 2)  1   1   2   2   3   3
≤ 3 (coin 5)  1   1   2   2   3   4   ← answer ways[3][5] = 4

Why it counts each combination exactly once

The claim is that ways[i][a] equals the number of multisets of the first i coin values that add up to a. Row 0 is right: the only multiset of no coins is the empty one, and it adds up to 0. For a later cell, split the multisets for a by whether they contain ci. Those that don't are exactly the multisets of the first i − 1 values, counted by ways[i-1][a]. Those that do are matched one-to-one with the multisets for a − ci of the first i values: remove one copy of ci in one direction, add one copy in the other. Both cells on the right were filled earlier (row above, or further left in the same row), so by induction they are already correct, and so is their sum. The two groups never overlap, so nothing is counted twice.

Another way to see it: the algorithm builds each way with its coins in the fixed order the coin values were brought in (all copies of the first value, then all copies of the second, and so on). Each multiset has exactly one such arrangement, so it is counted once.

Combinations or ordered sequences: the order of the loops matters

Each row only needs the row above and itself, so the table fits in one array. The classic one-dimensional version is:

ways[0..A] = 0;  ways[0] = 1
for each coin c:                  // coins in the OUTER loop
    for a = c to A:               // increasing a
        ways[a] = ways[a] + ways[a - c]
return ways[A]

Just before the update, ways[a] still holds the previous row's value ("don't use c"), and ways[a - c] was already updated in this pass ("use c again"), which is exactly the recurrence.

Swapping the two loops looks harmless but answers a different question:

seq[0..A] = 0;  seq[0] = 1
for a = 1 to A:                   // amounts in the OUTER loop
    for each coin c with c ≤ a:
        seq[a] = seq[a] + seq[a - c]
return seq[A]

Now, by the time seq[a] is computed, every seq[a - c] already counts sequences built from all the coins. The sum splits the ways by their last coin c, and the part before it is any sequence for a − c. Nothing fixes the order of the coins any more, so 2+1 (last coin 1) and 1+2 (last coin 2) are both counted: this counts ordered sequences (compositions), not combinations. With coins 1, 2, 5:

amount a        0   1   2   3   4   5
seq (ordered)   1   1   2   3   5   9      seq[5] = seq[4] + seq[3] + seq[0] = 5 + 3 + 1
combinations    1   1   2   2   3   4

They first differ at 3: the ordered count has 1+1+1, 1+2 and 2+1, while as combinations 1+2 and 2+1 are one way. For 5 the nine sequences are 5, the eight orderings of 1s and 2s adding up to 5 (1+1+1+1+1, four with one 2, three with two 2s). Choose Ordered sequences above to watch this version: it fills a single row, highlighting in green one source cell per coin, and ends by showing the combination counts underneath, with the cells where the two differ in pink.

Both questions are useful. "How many ways to climb 10 stairs taking 1 or 2 steps at a time?" is the ordered one, because taking 1 then 2 steps is different from 2 then 1. "How many ways to give change?" is the combinations one. Pick the loop order that matches the question.

Running time and space

The two-dimensional table has (n + 1)(A + 1) cells and each is filled with at most one addition, so the algorithm takes O(n·A) time and O(n·A) space. The one-dimensional versions do the same additions (the ordered one: for each of the A amounts, one addition per coin) in O(n·A) time, but keep only A + 1 numbers, so O(A) space. This is pseudo-polynomial: polynomial in the value of A, not in the number of digits needed to write it down. Listing the ways one by one, as the animation does for small cases, takes time proportional to how many there are, which grows very fast.

Common mistakes and edge cases

  • Wrong loop order. Amounts outside and coins inside counts ordered sequences. For combinations, coins must be the outer loop.
  • Starting with ways[0] = 0. Then every count is 0. The empty way makes amount 0.
  • Going downward in the 1-D inner loop (for a = A down to c). Then ways[a - c] is still the previous row's value, so each coin can be used at most once. That is a different problem (see the variants below).
  • Repeated coin values. Listing 2 twice counts 2+1 as two different ways. The page asks for different values.
  • Amount 0. The answer is 1 (the empty way), not 0.
  • A coin larger than the amount. It can never be used; its row just copies the row above (no "use" term), so it changes nothing.
  • No way at all. With coins 4 and 6 you cannot make 7: the answer is 0, which is correct, not an error.
  • Big numbers. Counts grow quickly (the ordered count for coins 1 to 5 and amount 20 is 400,096). For large amounts use big integers, or count modulo a prime if that is what is asked.

Variants

  • Fewest coins. Replace "add" by "minimum of (1 + …)", start with 0 for amount 0 and ∞ elsewhere: that is the Making Change page.
  • Each coin at most once. Use ways[i-1][a - c_i] (the row above) instead of ways[i][a - c_i], or in one dimension run the inner loop downward. This counts subsets that add up to A, just like 0/1 knapsack chooses subsets.
  • At most ki copies of coin i. ways[i][a] = the sum of ways[i-1][a - j·c_i] for j = 0, …, ki (with j·ci ≤ a).
  • Integer partitions. With coins 1, 2, …, A the combinations count is the number of ways to write A as a sum of positive integers, the partition number p(A); the ordered count is 2A−1.

Where it is used

Besides counting change, the same table counts integer partitions and the ways to reach a total from pieces of given sizes, for example the ways to score a total in a game with fixed point values. The ordered version counts things like staircase climbs, the ways to throw a given sum with repeated dice rolls, or the number of messages of a given length made of symbols of different durations. In combinatorics it computes the coefficients of the generating function 1 / ((1 − xc1) ⋯ (1 − xcn)). It is also a standard programming exercise ("Coin Change II" counts combinations, "Combination Sum IV" counts ordered sequences) exactly because the two loop orders are so easy to confuse.