{ }SolveLogs
⌕
Home / Dynamic Programming / #518
LeetCode #518 Medium

Coin Change II

Coin Change II is LeetCode 518 (Medium), also written Coin Change 2. You are given an array coins of distinct denominations and a target amount. Return the number of combinations of coins that add up to exactly amount.

  • Each coin can be used any number of times.
  • Order does not matter: the same coins in a different order count as one combination.
  • If no combination reaches the amount, return 0.
Constraints
  • 1 <= coins.length <= 300
  • 1 <= coins[i] <= 5000
  • All the values of coins are unique.
  • 0 <= amount <= 5000
dpknapsack
Open on LeetCode ↗
02

Intuition

Counting combinations means 2+2+1 and 1+2+2 are the same answer, so the danger is counting one combination several times. The fix is to fix an order: decide how many of the first coin, then the second, and so on. With the coins in a fixed order, each combination has only one way to be built.

When a new coin c joins, the ways to make an amount split cleanly into two groups: those that never use c, which are already counted, and those that use it at least once, which are a way to make the amount minus c with one more c on top. Adding the groups gives the number of ways to make change, each combination counted once.

How to spot this pattern

This is the number of ways to make change problem. Count the ways to reach a total from reusable items where order does not matter. That is the counting form of the unbounded knapsack. The tell is the word combinations: put the items in the outer loop. If the question counted ordered sequences, the amount would go outside instead.

03

Approach

Try it first

Before reading on, list by hand the ways to make 5 from [1, 2, 5]. Then try dp[a] += dp[a - c] with the amount loop outside. Why does it give a bigger number?

Two ways to solve it

1-D DP arrayBest
Time O(amount × n)Space O(amount)

Keep one array dp[a] and fold the coins in one at a time with dp[a] += dp[a - c].

  • Space: a single row of amount + 1 counts.
  • Speed: the same additions as the table, with less memory.
  • Catch: the coin loop must stay outside the amount loop.

This is the optimised version to write in an interview.

Solution & demo ↓
2-D DP table
Time O(amount × n)Space O(amount × n)

Row i counts the ways to make each amount with only the first i coins: skip coin i, or use it once more.

  • Space: n + 1 rows of amount + 1 counts.
  • Speed: the same additions as the 1-D array.
  • Readability: every stage of the count stays visible.

The clearest way to see the recurrence before shrinking it.

Code ↓

Each row reads only itself and the row above, so the table collapses into one array with the same answer and the same time. The steps, code and live demo follow the 1-D array, and the 2-D table code is further down.

1

Define the state

dp[a] = the number of combinations that make amount a using only the coins processed so far. The array has amount + 1 entries and is reused across coins, so each pass upgrades every count to include one more coin type.

2

Set the base case

dp[0] = 1: there is exactly one way to make 0, the empty combination. Every other entry starts at 0. If dp[0] were 0, nothing could ever be counted.

3

Loop over coins outside, amounts inside

For each coin c, run a from c to amount and add dp[a] += dp[a - c]. The old dp[a] is the ways without c; dp[a - c], already updated in this pass, is the ways that use c at least once, which is what lets c repeat. Keep the coin loop outside: swapping the loops counts orderings, so 1+2 and 2+1 would both be counted.

4

Return dp[amount]

After the last coin, dp[amount] holds every combination counted once, since each one was built in the single coin order the loops allow. If no coins can reach the amount, it stays 0, which is the correct answer rather than an error.

04

Coin Change II solution in Python | C++ | Java

▶1class Solution:
▶2 def change(self, amount: int, coins: List[int]) -> int:
▶3 dp = [1] + [0] * amount
▶4 for c in coins: # coins outside: each combination counted once
▶5 for a in range(c, amount + 1):
▶6 dp[a] += dp[a - c]
▶7 return dp[amount]
012345amountno coins100000
dp[0]1the empty combination
dp[1..5]0no coins allowed yet
Start with no coins allowed. dp[a] = the number of combinations that make amount a. With no coins, only amount 0 can be made, in exactly one way: take nothing. That 1 is what every combination grows from.
012345amountno coins100000+ coin 111
coin1pass 1 of 3
without 10cell above: ways with earlier coins only
with 11cell 1 to the left, same row
dp[1]10 + 1
Ways to make 1 = ways that use no coin 1 (0, from the row above) + ways that use at least one coin 1 (1: make 0 with coins up to 1, then add one 1). Reading the left cell from this row is what lets coin 1 be used more than once.
012345amountno coins100000+ coin 1111
coin1pass 1 of 3
without 10cell above: ways with earlier coins only
with 11cell 1 to the left, same row
dp[2]10 + 1
Ways to make 2 = ways that use no coin 1 (0, from the row above) + ways that use at least one coin 1 (1: make 1 with coins up to 1, then add one 1). Reading the left cell from this row is what lets coin 1 be used more than once.
012345amountno coins100000+ coin 11111
coin1pass 1 of 3
without 10cell above: ways with earlier coins only
with 11cell 1 to the left, same row
dp[3]10 + 1
Ways to make 3 = ways that use no coin 1 (0, from the row above) + ways that use at least one coin 1 (1: make 2 with coins up to 1, then add one 1). Reading the left cell from this row is what lets coin 1 be used more than once.
012345amountno coins100000+ coin 111111
coin1pass 1 of 3
without 10cell above: ways with earlier coins only
with 11cell 1 to the left, same row
dp[4]10 + 1
Ways to make 4 = ways that use no coin 1 (0, from the row above) + ways that use at least one coin 1 (1: make 3 with coins up to 1, then add one 1). Reading the left cell from this row is what lets coin 1 be used more than once.
012345amountno coins100000+ coin 1111111
coin1pass 1 of 3
without 10cell above: ways with earlier coins only
with 11cell 1 to the left, same row
dp[5]10 + 1
Ways to make 5 = ways that use no coin 1 (0, from the row above) + ways that use at least one coin 1 (1: make 4 with coins up to 1, then add one 1). Reading the left cell from this row is what lets coin 1 be used more than once.
012345amountno coins100000+ coin 1111111+ coin 2112
coin2pass 2 of 3
without 21cell above: ways with earlier coins only
with 21cell 2 to the left, same row
dp[2]21 + 1
Ways to make 2 = ways that use no coin 2 (1, from the row above) + ways that use at least one coin 2 (1: make 0 with coins up to 2, then add one 2). Reading the left cell from this row is what lets coin 2 be used more than once.
012345amountno coins100000+ coin 1111111+ coin 21122
coin2pass 2 of 3
without 21cell above: ways with earlier coins only
with 21cell 2 to the left, same row
dp[3]21 + 1
Ways to make 3 = ways that use no coin 2 (1, from the row above) + ways that use at least one coin 2 (1: make 1 with coins up to 2, then add one 2). Reading the left cell from this row is what lets coin 2 be used more than once.
012345amountno coins100000+ coin 1111111+ coin 211223
coin2pass 2 of 3
without 21cell above: ways with earlier coins only
with 22cell 2 to the left, same row
dp[4]31 + 2
Ways to make 4 = ways that use no coin 2 (1, from the row above) + ways that use at least one coin 2 (2: make 2 with coins up to 2, then add one 2). Reading the left cell from this row is what lets coin 2 be used more than once.
012345amountno coins100000+ coin 1111111+ coin 2112233
coin2pass 2 of 3
without 21cell above: ways with earlier coins only
with 22cell 2 to the left, same row
dp[5]31 + 2
Ways to make 5 = ways that use no coin 2 (1, from the row above) + ways that use at least one coin 2 (2: make 3 with coins up to 2, then add one 2). Reading the left cell from this row is what lets coin 2 be used more than once.
012345amountno coins100000+ coin 1111111+ coin 2112233+ coin 5112234
coin5pass 3 of 3
without 53cell above: ways with earlier coins only
with 51cell 5 to the left, same row
dp[5]43 + 1
Ways to make 5 = ways that use no coin 5 (3, from the row above) + ways that use at least one coin 5 (1: make 0 with coins up to 5, then add one 5). Reading the left cell from this row is what lets coin 5 be used more than once.
012345amountno coins100000+ coin 1111111+ coin 2112233+ coin 5112234combinations11111211122154 combinations → return 4
answer4dp[5] after the last coin
Answer 4. The combinations are 1 + 1 + 1 + 1 + 1, 2 + 1 + 1 + 1, 2 + 2 + 1, 5. Each is counted once, because coins were added in a fixed order: a combination is only ever built as its smaller-coin part first.
012345amountno coins100000+ coin 1111111+ coin 2112233+ coin 5112234loops swapped112359loops swapped → 9, not 4
coins outer4combinations (correct)
amount outer9permutations (wrong here)
The classic mistake. With the amount loop outside, every amount tries every coin as the last one, so the same coins in a different order are counted again. That gives 9 instead of 4. Keep coins in the outer loop.
05

2-D DP table

dp[i][a] counts the combinations that make a from the first i coins. It copies the count from the row above (coin i unused), then adds dp[i][a - c] from its own row (coin i used again).

▶1class Solution:
▶2 def change(self, amount: int, coins: List[int]) -> int:
▶3 n = len(coins)
▶4 dp = [[0] * (amount + 1) for _ in range(n + 1)]
▶5 dp[0][0] = 1
▶6 for i in range(1, n + 1):
▶7 c = coins[i - 1]
▶8 for a in range(amount + 1):
▶9 dp[i][a] = dp[i - 1][a]
▶10 if a >= c:
▶11 dp[i][a] += dp[i][a - c]
▶12 return dp[n][amount]
06

Common pitfalls

Putting the amount loop outside

✗ Wrong
for a in range(1, amount + 1):
    for c in coins:
        if c <= a:
            dp[a] += dp[a - c]
✓ Right
for c in coins:
    for a in range(c, amount + 1):
        dp[a] += dp[a - c]

With the amount outside, each amount tries every coin as the last one, so 1+2+2, 2+1+2 and 2+2+1 are counted separately. For [1, 2, 5] and 5 it returns 9 instead of 4. That loop order answers Combination Sum IV.

Starting with dp[0] = 0

✗ Wrong
dp = [0] * (amount + 1)
✓ Right
dp = [1] + [0] * amount

Every combination is built by adding a coin to a smaller combination, and the smallest one is the empty combination for amount 0. Without that 1, every entry stays 0.

Looping the amount downwards

✗ Wrong
for c in coins:
    for a in range(amount, c - 1, -1):
        dp[a] += dp[a - c]
✓ Right
for c in coins:
    for a in range(c, amount + 1):
        dp[a] += dp[a - c]

Going downwards reads dp[a - c] from before coin c joined, so each coin can be used at most once (0/1 knapsack). Going upwards lets the same coin be reused, which this problem allows.

07

Edge cases

amount = 0

Return 1: the empty combination. dp[0] = 1 is returned directly.

Large intermediate counts

LeetCode guarantees the answer fits in a signed 32-bit integer, but intermediate entries can be larger. The C++ version uses unsigned long long for safety.

08

Complexity

Time
O(amount × n)
Space
O(amount)
n is the number of coin types. One array is reused across all coins; a 2-D table (one row per coin) is only needed to explain the idea.
09

Combinations vs permutations vs fewest coins

The same coins and the same dp[a - c] lookup answer three different questions. The loop order and the operation decide which.

ProblemCountsOperationLoop order[1,2,5], 5
Coin Change II (518)combinationsdp[a] += dp[a - c]coins outer4
Combination Sum IV (377)ordered sequencesdp[a] += dp[a - c]amount outer9
Coin Change (322)fewest coinsdp[a] = min(dp[a], dp[a - c] + 1)either1 (just 5)
10

Coin Change II FAQ

What does Coin Change II ask?

It asks how many different combinations of coins, each usable any number of times, add up to the amount. Order does not matter. For coins [1, 2, 5] and amount 5 the answer is 4: 5, 2+2+1, 2+1+1+1, 1+1+1+1+1.

How does the Coin Change II dynamic programming solution count combinations?
  • State: dp[a] = number of combinations that make a.
  • Base case: dp[0] = 1.
  • Recurrence: for each coin c, for a from c to amount, dp[a] += dp[a - c].
  • Why coins outside: coins are added in a fixed order, so each combination is built exactly once.
  • Complexity: O(amount × n) time, O(amount) space.
  • Example: [1, 2, 5], 5 gives 4.
Why does the loop order matter in Coin Change II?

With coins outside, a combination is always built in coin order, so it is counted once. With the amount outside, every coin is tried as the last coin at every amount, so each ordering is counted separately. For [1, 2, 5] and 5 that gives 9 instead of 4.

What is the difference between Coin Change and Coin Change II?

Coin Change (322) finds the minimum number of coins, using min. Coin Change II (518) counts the number of combinations, using +=. Both are unbounded knapsack DPs over the amount.

Why is dp[0] equal to 1?

There is exactly one way to make amount 0: choose no coins. Every other combination is that empty combination with coins added, so this 1 is what all the counts are built from.

← Prev · #516
Longest Palindromic Subsequence
Next · #530 →
Minimum Absolute Difference in BST