Start practising

Coin Change II

Medium Dynamic Programming Knapsack Original on LeetCode

Coin Change II is a medium dynamic programming problem solved with the knapsack pattern. The best approach, optimal (1d dp, coins outer), runs in O(amount · k) time and O(amount) space. Below are 2 approaches in Java, from recursion over coins up.

Problem

Given coin values and an amount, return the number of combinations of coins that add up to the amount. Each coin can be used any number of times, and order does not matter.

Examples

Example 1

Input
amount = 5, coins = [1, 2, 5]
Output
4
Why
5, 2+2+1, 2+1+1+1, 1+1+1+1+1.

Example 2

Input
amount = 3, coins = [2]
Output
0

Constraints

  • 1 <= coins.length <= 300; 0 <= amount <= 5000.
  • Count combinations, not orderings: 1+2 and 2+1 are the same.

Animated walkthrough

A narrated, step-by-step animation that builds the solution from the idea up. Press play, or step through it at your own pace.

Concepts first, then the problem and every approach, step by step.

Space to play or pause · ← → to jump a step · click or drag the bar to seek

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the Java code.

ApproachTimeSpace
Recursion over coinsexponentialO(amount)
Optimal (1D DP, coins outer)O(amount · k)O(amount)

1Recursion over coins

Timeexponential
SpaceO(amount)

At coin i, either use it again (stay at i) or move on to coin i + 1. Moving forward only is what prevents counting permutations.

  1. f(i, a): a == 0 → 1; i == n or a < 0 → 0.
  2. f(i, a - coins[i]) + f(i + 1, a).
Java
class Solution {
    public int change(int amount, int[] coins) {
        return f(coins, 0, amount);
    }

    private int f(int[] coins, int i, int a) {
        if (a == 0) return 1;
        if (i == coins.length || a < 0) return 0;
        return f(coins, i, a - coins[i]) + f(coins, i + 1, a);
    }
}

2Optimal (1D DP, coins outer)

TimeO(amount · k)
SpaceO(amount)

dp[a] = number of combinations making a using the coins processed so far. Adding coin c: dp[a] += dp[a - c] for a from c upward.

  1. dp[0] = 1.
  2. For each coin c, for a in c..amount: dp[a] += dp[a - c].
Java
class Solution {
    public int change(int amount, int[] coins) {
        int[] dp = new int[amount + 1];
        dp[0] = 1;
        for (int c : coins)
            for (int a = c; a <= amount; a++) dp[a] += dp[a - c];
        return dp[amount];
    }
}

Edge cases to test

  • amount = 0 (one way: use nothing)

Hints

Hint 1

Put the coin loop outside the amount loop. That counts each combination once, in coin order, instead of every permutation.

FAQ

What is the best time complexity for Coin Change II?

Optimal (1D DP, coins outer) runs in O(amount · k) time and O(amount) extra space.

Which pattern does Coin Change II use?

It is a dynamic programming problem that uses the knapsack pattern. Other problems with the same pattern: 0 - 1 Knapsack Problem, Fractional Knapsack, Knapsack with Duplicate Items.

Is there a brute force solution for Coin Change II?

Yes. Recursion over coins takes exponential time and O(amount) space. At coin i, either use it again (stay at i) or move on to coin i + 1.

Which edge cases should I test for Coin Change II?

amount = 0 (one way: use nothing).