Coin Change II

medium2D Dynamic Programming30 stepsJava · Python · C++

Count the combinations of coins (unlimited supply) that make amount. Process one coin type at a time: dp[a] += dp[a − coin]. Putting coins in the outer loop counts each combination once, regardless of order.

▶ Watch the animated trace

Traced input: amount = 5, coins = [1, 2, 5] → 4. Original problem: neetcode.io/problems/coin-change-ii

Complexity

BestO(S·k)

AverageO(S·k)

WorstO(S·k)

SpaceO(S)

S = amount, k = coin types.

Key idea

dp[0] = 1: one way to make 0 (use nothing).
Outer loop over coins means each combination is built in a fixed coin order.
Inner loop upward allows reusing the current coin.

Common mistakes

Swapping the loops counts permutations (1+2 and 2+1 separately).
Using min instead of sum (that's Coin Change I).

Solution

Java

int change(int amount, int[] coins) {
    int[] dp = new int[amount + 1];
    dp[0] = 1;
    for (int coin : coins) {
        for (int a = coin; a <= amount; a++) {
            dp[a] += dp[a - coin];
        }
    }
    return dp[amount];
}

Python

def change(amount: int, coins: List[int]) -> int:
    dp = [1] + [0] * amount
    for coin in coins:
        for a in range(coin, amount + 1):
            dp[a] += dp[a - coin]
    return dp[amount]

C++

int change(int amount, vector<int>& coins) {
    vector<long long> dp(amount + 1);
    dp[0] = 1;
    for (int coin : coins) {
        for (int a = coin; a <= amount; a++) {
            dp[a] += dp[a - coin];
        }
    }
    return dp[amount];
}

Edge cases

Each one has its own trace in the interactive view.

Case	Input	Answer
Impossible No combination of 2s makes 3.	`amount = 3, coins = [2]`	`0`
Amount 0 The empty combination.	`amount = 0, coins = [7]`	`1`
Single coin One coin.	`amount = 10, coins = [10]`	`1`