Coin Change, in depth: minimum coins and counting ways, loop order, reconstruction, greedy checks and the bugs that break each variant

Two questions, one table

Fix the input as a list of positive integer denominations coins, each usable any number of times, and a target A. The two questions are:

The base cases are the first trap. For minimum coins, zero coins make amount zero, so dp[0] = 0. For counting, there is exactly one way to make zero: choose nothing, so dp[0] = 1. Set the counting base to 0 and every entry stays 0; set it to 1 for the minimum variant and every answer is one too high.

Both are instances of the unbounded knapsack, where every item can be reused. If each coin may be used at most once the problem becomes 0/1 subset sum, covered below and in knapsack, in depth.

Variant 1: the fewest coins, worked by hand

Let dp[a] be the fewest coins that sum to a. The last coin used is some c with c <= a, and what remains, a - c, must itself be made optimally. So dp[a] = 1 + min over c of dp[a - c], taking only coins that fit and only remainders that are reachable.

Work it on coins {1, 5, 6, 9} and amount 11. Largest-coin-first takes 9, then 1 and 1: three coins. The table finds better:

Check the last cell by hand: candidates are dp[10] + 1 = 3 (coin 1), dp[6] + 1 = 2 (coin 5), dp[5] + 1 = 2 (coin 6) and dp[2] + 1 = 3 (coin 9). The minimum is 2, reached first through coin 5, so the answer is 5 + 6. Here is the code, with a sentinel for unreachable amounts and a second array that remembers the winning coin:

INF = float("inf")

def min_coins(coins, amount):
    dp = [0] + [INF] * amount          # dp[a] = fewest coins for a
    last = [-1] * (amount + 1)         # coin that achieved dp[a]
    for a in range(1, amount + 1):
        for c in coins:
            if c <= a and dp[a - c] + 1 < dp[a]:
                dp[a] = dp[a - c] + 1
                last[a] = c
    if dp[amount] == INF:
        return None, []
    picked, a = [], amount
    while a > 0:                       # walk the choices backwards
        picked.append(last[a])
        a -= last[a]
    return dp[amount], picked

print(min_coins([1, 5, 6, 9], 11))     # (2, [5, 6])
print(min_coins([4, 6], 7))            # (None, [])

For the minimum variant the loop order does not matter: putting coins outside and amounts inside gives the same table, because a minimum is the same whatever order the candidates are seen in. That freedom does not carry over to counting.

Rebuilding the coins

The last array costs O(A) extra memory and turns a number into an answer a caller can use, such as the actual coins to dispense. Without it you can re-scan: at amount a, find any coin with dp[a - c] == dp[a] - 1 and step down, at O(n) per step.

Two practical notes. First, ties: when several coins achieve the minimum, the strict < keeps the first one in input order, so sort the coins if you want a deterministic preference (for example, prefer larger coins so a cash drawer empties its big denominations first). Second, the walk back always terminates, because every recorded coin is positive and every remainder it leads to was itself reachable.

Variant 2: counting ways, and why loop order decides what you count

Now count. Let dp[a] be the number of ways to make a. The question that matters is: does 1 + 2 count as a different way from 2 + 1? In change-making it does not; a way is a multiset of coins. In other problems, such as counting step sequences up a staircase, order does matter. The same recurrence answers either question, and the only difference is which loop is outside.

def count_combinations(coins, amount):
    dp = [1] + [0] * amount
    for c in coins:                    # coins OUTSIDE
        for a in range(c, amount + 1):
            dp[a] += dp[a - c]
    return dp[amount]

def count_sequences(coins, amount):
    dp = [1] + [0] * amount
    for a in range(1, amount + 1):     # amounts OUTSIDE
        for c in coins:
            if c <= a:
                dp[a] += dp[a - c]
    return dp[amount]

print(count_combinations([1, 2, 5], 5))   # 4
print(count_sequences([1, 2, 5], 5))      # 9

Trace the combination count on coins {1, 2, 5} and amount 5. After processing coin 1 alone, every amount has one way: [1, 1, 1, 1, 1, 1]. Adding coin 2 gives dp[2] = 1 + dp[0] = 2, dp[3] = 1 + dp[1] = 2, dp[4] = 1 + dp[2] = 3 and dp[5] = 1 + dp[3] = 3, so the row is [1, 1, 2, 2, 3, 3]. Adding coin 5 gives dp[5] = 3 + dp[0] = 4. The four ways are 5, 2+2+1, 2+1+1+1 and 1+1+1+1+1.

Why does coins-outside count each multiset once? While processing coin c, the table only contains ways that use coins up to and including c. Every way is therefore built in one canonical order, with coins appearing in input order, and no rearrangement of it is ever generated separately. Put amounts outside and, at each amount, every coin may be the last one added after any arrangement of the rest, so 2+1+1+1, 1+2+1+1, 1+1+2+1 and 1+1+1+2 are all counted. The sequence count follows f(a) = f(a-1) + f(a-2) + f(a-5): f = 1, 1, 2, 3, 5, then f(5) = 5 + 3 + 1 = 9.

Neither number is wrong in itself. The bug is answering one question with the other's loop order, and because the outputs are plausible integers, only a hand-checked test catches it.

Bounded, 0/1 and other variants

Variants appear constantly in practice, and each changes one line:

The descending loop is the same trick that separates 0/1 from unbounded knapsack: ascending lets a value updated earlier in the same pass feed a later one, which means reusing the coin.

The same problem as a shortest path

The minimum variant is also a shortest-path problem. Treat each amount from 0 to A as a node and each coin as an edge from a to a + c with cost 1. The fewest coins is the shortest path from 0 to A, and because all edges cost the same, breadth-first search finds it level by level. See BFS on implicit graphs for the general pattern.

from collections import deque

def min_coins_bfs(coins, amount):
    if amount == 0:
        return 0
    seen = [False] * (amount + 1)
    seen[0] = True
    q = deque([0])
    steps = 0
    while q:
        steps += 1
        for _ in range(len(q)):
            a = q.popleft()
            for c in coins:
                b = a + c
                if b == amount:
                    return steps
                if b < amount and not seen[b]:
                    seen[b] = True
                    q.append(b)
    return None

BFS stops at the target, so when the answer is a few large coins it touches far fewer amounts than the table; in the worst case it visits them all. It cannot count ways, so the table stays the default.

When greedy is safe, and how to test it

Largest-coin-first is optimal for some coin systems and wrong for others; greedy algorithms, in depth explains why. A system where greedy is always optimal is called canonical. Most national currencies are canonical, but loyalty-point bundles, postage stamps and game currencies often are not, and you should not assume either way.

You can test a system mechanically. Kozen and Zaks showed that if greedy fails for a system at all, its smallest failing amount is below the sum of the two largest denominations. So comparing greedy against the DP for every amount up to that bound settles the question. Pearson later gave a polynomial-time algorithm in the number of coins; for small sets the brute-force check is simpler and easy to trust.

def greedy_count(coins, amount):
    n = 0
    for c in sorted(coins, reverse=True):
        n += amount // c
        amount %= c
    return n if amount == 0 else None

def first_greedy_failure(coins):
    """Smallest amount where greedy is not optimal, or None if canonical.
    Assumes 1 is a coin, so every amount is reachable."""
    top = sorted(coins)[-2:]
    bound = sum(top)
    dp = [0] + [float("inf")] * bound
    for a in range(1, bound + 1):
        dp[a] = 1 + min(dp[a - c] for c in coins if c <= a)
        if greedy_count(coins, a) != dp[a]:
            return a
    return None

print(first_greedy_failure([1, 5, 10, 25]))   # None
print(first_greedy_failure([1, 5, 6, 9]))     # 11

For {1, 5, 6, 9}, amount 10 passes (9 + 1 and 5 + 5 are both two coins); 11 fails, three coins against two. Run the check once when a coin set is configured and fall back to the DP whenever it fails.

Cost, shortcuts and top-down versus bottom-up

Both variants take O(n × A) time and O(A) memory, where n is the number of denominations and A the amount. That is pseudo-polynomial: polynomial in the value of A but exponential in the number of bits needed to write it down. An amount of a million with ten coins is ten million cheap steps; an amount of 10^12 is out of reach for the table, though BFS or a mathematical shortcut might still work.

Two cheap checks run before the table. If the amount is not divisible by the greatest common divisor of the coins, no combination exists and you can return immediately. And if all coins share a factor g, divide the coins and the amount by g first: the answers are unchanged and the table shrinks by a factor of g.

Top-down memoisation visits only reachable amounts but recurses up to A frames deep, which overflows Python's default stack for amounts in the low thousands. Bottom-up has no depth limit, so it is the default.

Failure modes

Each of these has shipped in real code:

• Sentinel overflow. In Java or C, using Integer.MAX_VALUE as infinity and then adding 1 wraps to a large negative number, which then wins every minimum. Use amount + 1 as the sentinel, since no answer can need more coins than that when the smallest coin is at least 1.
• Wrong loop order for counting. Amount-outside counts ordered sequences. Test {1, 2, 5} for amount 5: combinations must give 4.
• Wrong base case. dp[0] = 0 for counting makes everything 0; dp[0] = 1 for minimum makes everything off by one.
• Duplicate denominations. Input [1, 2, 2] double-counts ways using a 2. Deduplicate first.
• Zero or negative coins. These make the count infinite or the search endless. Validate the input.
• Count overflow. The number of ways grows exponentially; fixed-width integers wrap silently. Use arbitrary precision or reduce modulo the stated prime.
• Unreachable amount reported as a number. Returning infinity, -1 or amount + 1 to a caller that expects a coin count produces nonsense downstream. Make unreachable a distinct, typed result.

What to do next

Work through this list with your own code open:

1. Write down which question you are answering: fewest coins, number of multisets, or number of ordered sequences.
2. Set the base case to match: 0 for minimum, 1 for counting.
3. For counting, put the coin loop outside unless order matters; add a comment saying which one you chose and why.
4. Pick a safe sentinel (amount + 1) and return a distinct result for unreachable amounts.
5. Keep a last-coin array if a caller needs the coins, and sort the coins to make tie-breaking deterministic.
6. Add the four regression tests from this page: {1, 5, 6, 9} for 11 gives 2; {4, 6} for 7 is unreachable; {1, 2, 5} for 5 gives 4 combinations and 9 sequences.
7. If you want greedy for speed, run the canonical check up to the sum of the two largest coins when the coin set is loaded, and fall back to the DP if it fails.
8. Before building a table for a huge amount, divide out the gcd and consider BFS or a different formulation.