Coin change problem in Python

Given some coin values and an amount, find the smallest number of coins that adds up to exactly that amount. You can use each coin value as many times as you like. This program also tells you which coins to use.

The program

def fewest_coins(amount, coins):
    # best[x] is the shortest list of coins that adds up to x, or None if there is none
    best = [None] * (amount + 1)
    best[0] = []
    for x in range(1, amount + 1):
        for coin in coins:
            if coin <= x and best[x - coin] is not None:
                candidate = best[x - coin] + [coin]
                if best[x] is None or len(candidate) < len(best[x]):
                    best[x] = candidate
    return best[amount]


print(fewest_coins(11, [1, 5, 6, 9]))
print(fewest_coins(63, [1, 5, 10, 25]))
print(fewest_coins(0, [1, 5]))
print(fewest_coins(3, [5, 10]))

[6, 5]
[25, 25, 10, 1, 1, 1]
[]
None

How it works

This method is called dynamic programming: you solve the problem for every smaller amount first, and use those answers to build the next one.

• best[0] is an empty list, because 0 needs no coins.
• For each amount x from 1 upwards, the program tries each coin as the last coin. If you use a coin of 5 last, the rest is the best answer for x - 5, which is already known.
• It keeps the shortest of those lists. If no coin fits, best[x] stays None.
• For 3 with coins of 5 and 10, there is no answer, so the function returns None.

The number of steps grows with amount × number of coins, so even an amount of 10,000 takes well under a second.

Why not always take the largest coin?

Taking the largest coin that fits is called the greedy method. It gives the right answer for normal currencies, but not for every set of coins:

def greedy_coins(amount, coins):
    used = []
    for coin in sorted(coins, reverse=True):
        while amount >= coin:
            used.append(coin)
            amount -= coin
    return used


print(greedy_coins(11, [1, 5, 6, 9]))
print(greedy_coins(63, [1, 5, 10, 25]))

[9, 1, 1]
[25, 25, 10, 1, 1, 1]

For 11, greedy takes 9 first and then needs two coins of 1: three coins. The program above found [6, 5], only two coins, by skipping the largest coin. For 63 with the coins 1, 5, 10 and 25, greedy gives the same answer as the program, because those coin values are designed so that greedy always works.