LeetCode 518: Coin Change II

Problem Restatement

We are given an integer amount and an array coins.

Each value in coins is a coin denomination.

We have an infinite number of each coin type.

We need to return the number of different combinations that can make up exactly amount.

If the amount cannot be formed, return 0.

The order of coins does not matter. For example, [1, 2, 2] and [2, 1, 2] represent the same combination.

The official problem asks for the number of combinations that make up the amount, with unlimited coins of each denomination. The answer is guaranteed to fit in a signed 32-bit integer.

Input and Output

Function shape:

class Solution:
    def change(self, amount: int, coins: List[int]) -> int:
        ...

Examples

Example 1:

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

The combinations are:

5
2 + 2 + 1
2 + 1 + 1 + 1
1 + 1 + 1 + 1 + 1

So the answer is:

4

Example 2:

amount = 3
coins = [2]

Using only coin 2, we cannot form 3.

So the answer is:

0

Example 3:

amount = 10
coins = [10]

There is exactly one way:

10

So the answer is:

1

First Thought: Try All Choices

For each coin, we can choose:

1. Use it.
2. Skip it.

Since each coin can be used unlimited times, using a coin does not move us to the next coin. We may use it again.

A recursive state could be:

dfs(index, remaining)

where index is the current coin type and remaining is the amount left.

The choices are:

use coins[index]
skip coins[index]

This works conceptually, but without memoization it recomputes many states.

Problem With Plain Recursion

The same remaining amount can be reached in many ways.

For example, with:

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

the state “make amount 3 using coins [1, 2, 5]” can appear through several recursive paths.

This overlapping work suggests dynamic programming.

Key Insight

We need to count combinations, not permutations.

That means the order of using coins must be fixed.

If we process coins one by one, then each combination is counted exactly once.

For each coin, update the number of ways to form each amount.

Let:

dp[x]

mean:

the number of combinations that form amount x using the coins processed so far

Initialize:

dp[0] = 1

There is one way to make amount 0: choose no coins.

For each coin, we scan amounts from coin up to amount.

When processing coin c, the transition is:

dp[x] += dp[x - c]

This means every way to form x - c can be extended by adding one coin c.

Algorithm

Create a DP array of length amount + 1.

Initialize:

dp[0] = 1

Then for each coin c in coins:

1. For every value x from c to amount
2. Add dp[x - c] into dp[x]

Finally, return:

dp[amount]

The loop order is important.

Coins are the outer loop.

Amounts go forward in the inner loop.

This allows unlimited use of the current coin while preventing different orders of the same combination from being counted multiple times.

Correctness

After processing some prefix of the coin list, dp[x] stores the number of combinations that form amount x using only those processed coins.

Initially, before any real coin is processed, dp[0] = 1 because there is exactly one way to form amount 0: use no coins. Every positive amount has zero ways.

When processing coin c, for each amount x >= c, every existing combination that forms x - c can be extended by adding one coin c. Since the inner loop moves forward, dp[x - c] already includes combinations that may use coin c multiple times.

Adding dp[x - c] to dp[x] therefore counts exactly the combinations for amount x that use at least one coin c.

Combinations that do not use coin c were already present in dp[x].

Because coins are processed in a fixed order, the same multiset of coins is counted once, not once per ordering.

After all coins are processed, dp[amount] is exactly the number of combinations that form amount.

Complexity

Here, n = len(coins).

Implementation

from typing import List

class Solution:
    def change(self, amount: int, coins: List[int]) -> int:
        dp = [0] * (amount + 1)
        dp[0] = 1

        for coin in coins:
            for value in range(coin, amount + 1):
                dp[value] += dp[value - coin]

        return dp[amount]

Code Explanation

Create the DP array:

dp = [0] * (amount + 1)

Set the base case:

dp[0] = 1

This represents using no coins.

Process one coin type at a time:

for coin in coins:

For each amount that can use this coin:

for value in range(coin, amount + 1):

add the number of ways to form the remaining amount:

dp[value] += dp[value - coin]

At the end:

return dp[amount]

returns the number of combinations for the target amount.

Testing

def test_change():
    s = Solution()

    assert s.change(5, [1, 2, 5]) == 4
    assert s.change(3, [2]) == 0
    assert s.change(10, [10]) == 1
    assert s.change(0, [1, 2, 5]) == 1
    assert s.change(4, [1, 2]) == 3
    assert s.change(5, [5, 1, 2]) == 4

    print("all tests passed")

Test meaning: