Coin Change II

MediumDynamic Programming · Unbounded Knapsack🧩 Knapsack DP LeetCode #518 ↗Updated Oct 30, 2026

Problem

You have an unlimited supply of each coin denomination in coins. Count how many different combinations of coins add up exactly to amount. Order does not matter: 1+2 and 2+1 are the same combination. If no combination works, return 0.

Inputamount=5, coins=[1,2,5]Output4

Inputamount=3, coins=[2]Output0

Inputamount=10, coins=[10]Output1

1 ≤ coins.length ≤ 300 · 1 ≤ coins[i] ≤ 5000 (distinct) · 0 ≤ amount ≤ 5000 · answer fits in a 32-bit int

Try it yourself

Java

class Solution {
    public int change(int amount, int[] coins) {
        
    }
}

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

Avoid counting permutations by deciding coins one type at a time: put the coin loop outside the amount loop. Then every combination is built in a fixed coin order, so dp[j] += dp[j - coin] counts each one exactly once.

PatternKnapsack DP

Instinct Choose items to hit or stay under a target sum (can it be done, best value, fewest items, how many ways) - index a DP array by the remaining capacity.

Memory hack Once? Walk back. Many? Walk forward. Each item used at most once loops capacity downward; reusable items loop it upward.

Open the Knapsack DP guide →

Approaches

Brute ForceRecursion (Take / Skip Coin)

Time O(2^{n + A})Space O(n + A)

At coin index either skip it for good (move to index+1) or take one more of it (stay on index, reduce the amount). Fixing the coin order this way never produces the same combination twice. Each call moves the index or lowers the amount, so depth ≤ n + A (A = amount).

Java

public int change(int amount, int[] coins) {
    return countWays(coins, amount, 0);
}
private int countWays(int[] coins, int remaining, int index) {
    if (remaining == 0) return 1;                       // valid combination
    if (remaining < 0 || index == coins.length) return 0;
    int skip = countWays(coins, remaining, index + 1);
    int take = countWays(coins, remaining - coins[index], index);
    return skip + take;
}

Correct and order-safe, but the same (index, remaining) states are recomputed exponentially.

Better2D DP Table

Time O(n · A)Space O(n · A)

Tabulate the recursion: dp[i][j] = ways to form j using only the first i coin types. Either coin i is unused (dp[i-1][j]) or at least one is used, leaving j - coin with coin i still allowed (dp[i][j-coin]). dp[i][0] = 1 (empty set).

Java

public int change(int amount, int[] coins) {
    int n = coins.length;
    int[][] dp = new int[n + 1][amount + 1];
    for (int i = 0; i <= n; i++) dp[i][0] = 1;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= amount; j++) {
            dp[i][j] = dp[i - 1][j];                    // without coin i
            if (j >= coins[i - 1]) dp[i][j] += dp[i][j - coins[i - 1]];
        }
    }
    return dp[n][amount];
}

Polynomial and easy to derive from the recursion, but keeps the whole table.

Optimal1D DP (Coins Outer Loop)

Time O(n · A)Space O(A)

Row i only reads row i-1 at the same column and row i to the left, so one array suffices. Iterating j upward lets dp[j-coin] already include the current coin — exactly the “use it again” (unbounded) case.

Java

public int change(int amount, int[] coins) {
    int[] dp = new int[amount + 1];   // dp[j] = ways to make j
    dp[0] = 1;
    for (int coin : coins)            // coins OUTER => combinations
        for (int j = coin; j <= amount; j++)
            dp[j] += dp[j - coin];
    return dp[amount];
}

Dry runamount=5, coins=[1,2,5] (dp[0..5])

changed

init
1

0

0

0

0

0

dp[0]=1 (no coins)
coin=1
1

1

1

1

1

1

only 1s: one way each
coin=2
1

1

2

2

3

3

dp[j] += dp[j-2]
coin=5
1

1

2

2

3

4

dp[5] += dp[0] → 4 ✔

Same time, linear memory — the standard unbounded-knapsack counting answer.

Pro tip

Swap the loops (amount outer, coins inner) and you count permutations instead — that is Combination Sum IV (377).

At a glance

Level	Approach	Time	Space
Brute Force	Recursion (Take / Skip Coin)	`O(2^{n + A})`	`O(n + A)`
Better	2D DP Table	`O(n · A)`	`O(n · A)`
Optimal	1D DP (Coins Outer Loop)	`O(n · A)`	`O(A)`

Common pitfalls

Amount loop outside the coin loop — counts 1+2 and 2+1 separately.
Iterating j downward in 1D — turns it into 0/1 knapsack (each coin once).
Forgetting dp[0] = 1 — every answer becomes 0 (and amount=0 must return 1).

Interview tips

Contrast with Coin Change (322): min coins uses min, this one uses +.
Explain why the loop order matters before writing code.
Derive 1D from 2D by noting which cells each row reads.

Pattern

Unbounded knapsack (counting) → items reusable, count combinations reaching an exact target.

My notes saved in this browser