Coin Change II

The problem

coins lists the coin values you may use, all different, and you have as many coins of each value as you need. Return the number of combinations of coins that add up to exactly amount. Two combinations are the same when they use each value the same number of times, whatever the order. If amount cannot be made, return 0. An amount of 0 can be made in exactly one way: with no coins.

What to write

function solve(amount: number, coins: number[]): number

Input
amount = 5
coins = [1,2,5]

Output
4

Input
amount = 3
coins = [2]

Output
0

Constraints

Coin denominations are distinct positive integers; amount is nonnegative and the answer fits a signed 32-bit integer.

Hints

Each hint gives away a little more. Open one only when you need it.

1. Hint 1: Use the constraints

   Order does not matter: 1 + 2 + 2 and 2 + 1 + 2 are one combination. The limits only promise that the answer fits in 32 bits, so it can be as large as about two billion. You have to count the combinations without listing them one by one.

2. Hint 2: Ask a smaller question

   Take amount 4 with the coins 1 and 2. Write down every combination by hand, making sure 1 + 1 + 2 and 2 + 1 + 1 are not both on your list. What rule did you follow to avoid writing the same combination twice?

3. Hint 3: Name the pattern

   To count each combination once, handle the coins in a fixed order: finish the first coin, then the second, and so on, and after each coin know the number of ways to make every sum. Items taken one at a time against a total to reach is knapsack dynamic programming, named after packing a bag up to a limit. Read the lesson on knapsack dynamic programming.

4. Hint 4: State the invariant

   Keep one count per sum from 0 to amount. After a coin is finished, the count for a sum is the number of combinations that make that sum from the coins handled so far. While a coin is being handled, the counts below the current sum already include that coin, so the coin can be used again.

5. Hint 5: Sketch the pseudocode

   ways = a list of amount + 1 zeros, with ways[0] = 1. For each coin: for each sum from the coin's value up to amount: ways[sum] = ways[sum] + ways[sum - coin]. Return ways[amount].

Solution

From here on the page gives the method away. If you are still solving, go back to the hints.

Approach

Process one denomination at a time, extending smaller sums upward. This counts combinations without counting different coin orders separately.

The slow way

Build every pile of coins by adding one coin at a time until the sum reaches amount or passes it. That finds every way to pay, but 1 + 2 + 2 and 2 + 1 + 2 turn up separately. For 5 with the coins 1, 2 and 5 it counts 9 where the answer is 4, and the number of piles grows fast.

The insight

Handle the coins in a fixed order, and each combination is built in exactly one way. With one more coin allowed, the combinations for a sum are the old ones plus those that use the new coin at least once. Take one such coin away and a combination for the smaller sum remains. Filling a table of sums coin by coin like this is knapsack dynamic programming.

Step by step

1. Keep a count of ways for every sum from 0 to amount, all 0 at first. The count for a sum will be the number of combinations that make that sum from the coins handled so far. Before any coin is handled, no sum above 0 can be made, so those counts start at 0.
2. Sum 0 can be made in one way: with no coins. Using no coins at all is a real combination, and the only one that adds up to 0. Every other count grows out of this 1. Without it, all counts would stay 0.
3. Bring in the coins one at a time. A coin is finished completely before the next one starts. So each combination is counted once, in the order the coins are listed, and never again with its coins in another order.
4. Walk the sums upward, starting at the coin's own value. A sum smaller than the coin cannot contain the coin, so that sum's count does not change. Going upward means the smaller sums are updated first, and they already count combinations that use this coin.
5. Add the ways to make the sum that is one such coin smaller. The count already there covers every combination without this coin. A combination with this coin is one such coin plus a combination for the smaller sum, whose count is up to date. The two groups share nothing, so add them.
6. Return the count kept for amount. After the last coin, the count for a sum covers all the coins. When no combination makes amount, the count for amount is still the 0 it started with.

The same numbered steps are the comments in each solution.

function solve(amount, coins) {
  // 1. Keep a count of ways for every sum from 0 to amount, all 0 at first
  const dp = Array(amount + 1).fill(0);
  // 2. Sum 0 can be made in one way: with no coins
  dp[0] = 1;
  // 3. Bring in the coins one at a time
  for (const coin of coins)
    // 4. Walk the sums upward, starting at the coin's own value
    for (let sum = coin; sum <= amount; sum++)
      // 5. Add the ways to make the sum that is one such coin smaller
      dp[sum] += dp[sum - coin];
  // 6. Return the count kept for amount
  return dp[amount];
}

function solve(amount: number, coins: number[]): number {
  // 1. Keep a count of ways for every sum from 0 to amount, all 0 at first
  const dp = Array(amount + 1).fill(0);
  // 2. Sum 0 can be made in one way: with no coins
  dp[0] = 1;
  // 3. Bring in the coins one at a time
  for (const coin of coins)
    // 4. Walk the sums upward, starting at the coin's own value
    for (let sum = coin; sum <= amount; sum++)
      // 5. Add the ways to make the sum that is one such coin smaller
      dp[sum] += dp[sum - coin];
  // 6. Return the count kept for amount
  return dp[amount];
}

def solve(amount, coins):
    # 1. Keep a count of ways for every sum from 0 to amount, all 0 at first
    dp = [0] * (amount + 1)
    # 2. Sum 0 can be made in one way: with no coins
    dp[0] = 1
    # 3. Bring in the coins one at a time
    for coin in coins:
        # 4. Walk the sums upward, starting at the coin's own value
        for total in range(coin, amount + 1):
            # 5. Add the ways to make the sum that is one such coin smaller
            dp[total] += dp[total - coin]
    # 6. Return the count kept for amount
    return dp[amount]

Example 1, traced

Input
amount = 5
coins = [1,2,5]

Output
4

Why it works

After each coin, the count for a sum is the number of combinations that make that sum from the coins handled so far. Handling a coin splits those combinations by whether they use the coin. Without it: the count that was already there. With it: remove one such coin and a combination for the smaller sum remains, counted earlier in the same walk. No combination falls in both groups.

Time and space

Time O(amount · coins.length), extra space O(amount). For each coin the inner loop visits at most amount sums and does one addition at each, so the time is O(amount · coins.length). The only storage is the list of amount + 1 counts, so the space is O(amount).

n and m are input sizes, h is a tree's height, V and E are a graph's vertices and edges. The bounds describe this reference solution.

Watch out

• Keep the coins in the outer loop. With the sums outside and the coins inside, the same coins are counted again in every order: 5 with the coins 1, 2 and 5 gives 9 instead of 4.
• Walk the sums upward. Going downward reads counts that do not include the current coin yet, so each coin is used at most once: the same example gives 1, because only the single 5 is found.
• Set the count for sum 0 to 1 before the loops. If it stays 0, every addition adds 0 and the answer is 0 for every input, even for amount 0, where the answer should be 1.

Pattern

Knapsack dynamic programming. Builds on Coin Change and Partition Equal Subset Sum.

Keep going