Coin Change Problem

The problem, simply

You get a list of coin values, like [1, 2, 3], and an amount sum, like 4. You have as many coins of each value as you want. Count how many different handfuls of coins add up to exactly sum.

Order does not matter. 1 + 3 and 3 + 1 are the same handful, so they count once.

(There is a sister problem: find the fewest coins that pay sum. It is covered further down, because interviewers like to ask both.)

A story to remember it

Picture it

Examples

Way 1: the simple way

Look at the last kind of coin. You have two choices:

1. Use one more of it. The amount goes down, and you may still use it again.
2. Never use it again. Same amount, one fewer kind of coin.

Add the counts of both choices. When the amount hits 0 you found a handful (count 1). When no kinds of coin are left and money is still owed, that is a dead end (count 0).

class Solution {
    // ways to pay sum using only coins[0..i-1]
    long ways(int[] coins, int i, int sum) {
        if (sum == 0) return 1;            // paid exactly: one handful
        if (i == 0) return 0;              // no coin kinds left, money still owed
        long w = 0;
        if (coins[i - 1] <= sum) {
            w += ways(coins, i, sum - coins[i - 1]);   // use one more of this coin
        }
        w += ways(coins, i - 1, sum);                  // never use this coin again
        return w;
    }

    public long count(int[] coins, int sum) {
        return ways(coins, coins.length, sum);
    }
}

How long it takes: every step either lowers the amount or drops a coin kind, and branches in two, so it can reach O(2^(n + sum)) calls. Extra room: the chain of waiting calls, O(n + sum).

Way 2: the clever way

The tree asks "pay 2 with only 1s" and "pay 1 with only 1s" more than once. Write each answer in a table instead. Row r uses the first r kinds of coin. Column s is the amount. Each box is:

box above (do not use this coin) + box to the left by one coin (use one more of this coin).

The row only needs itself and the row above, so we keep one array dp and update it in place, from left to right. Left to right is right here: the box to the left is already in the new row, and that is what lets us use the same coin again.

1. dp[0] = 1, everything else 0.
2. For each coin, for s from coin up to sum: dp[s] += dp[s - coin].
3. The answer is dp[sum].

class Solution {
    public long count(int[] coins, int sum) {
        long[] dp = new long[sum + 1];   // dp[s] = handfuls that pay s
        dp[0] = 1;                       // pay nothing: one way
        for (int coin : coins) {         // bring in one kind of coin at a time
            for (int s = coin; s <= sum; s++) {
                dp[s] += dp[s - coin];   // use one more of this coin
            }
        }
        return dp[sum];
    }
}

How long it takes: for each of the n coins we walk the sum + 1 cups, O(n * sum). Extra room: one row of cups, O(sum).

Another way: the fewest coins

The sister question: what is the smallest number of coins that pays sum exactly? Return -1 if it cannot be done. Now each cup holds "fewest coins to pay this amount". To fill cup s, try every coin as the last coin you hand over: dp[s] = min(dp[s - coin] + 1).

import java.util.Arrays;

class Solution {
    public int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, amount + 1);     // bigger than any real answer
        dp[0] = 0;                       // paying 0 needs 0 coins
        for (int s = 1; s <= amount; s++) {
            for (int coin : coins) {
                if (coin <= s) dp[s] = Math.min(dp[s], dp[s - coin] + 1);
            }
        }
        return dp[amount] > amount ? -1 : dp[amount];
    }
}

For coins = [1, 2, 3], amount = 4 this gives 2 (3 + 1, or 2 + 2). It is also O(n * amount) time and O(amount) room. Do not grab the biggest coin first: with coins [1, 3, 4] and amount 6, greedy takes 4 + 1 + 1 (3 coins), but 3 + 3 is only 2.

Watch out for

• dp[0] must be 1 for counting (and 0 for the fewest coins version). Everything grows from it.
• Counts get big. Use long, or the modulo the judge asks for.
• In the fewest coins version, do not fill with Integer.MAX_VALUE. Adding 1 to it overflows to a negative number.

What interviewers ask next

• Count orders instead of handfuls (like climbing stairs with steps 1, 2, 3)? Swap the loops: amounts outside, coins inside.
• Each coin can be used at most once? Then it is the 0/1 knapsack: loop s from sum down to coin, so a coin cannot be reused in the same row.
• Print one fewest-coins handful. Remember which coin set each dp[s], then walk back from sum.
• When is greedy (biggest coin first) safe? For coin systems like 1, 5, 10, 25 it works. In general it does not, so use DP unless the coins are known to be safe.

Remember this

Grown-up words: the cups are the DP array, "use it again or never again" is the unbounded knapsack choice, the faded repeats are overlapping subproblems, handfuls are combinations, and orders are permutations.