LeetCode 518 - Coin Change II

LeetCode Problem 518

Difficulty: 🟡 Medium
Topics: Array, Dynamic Programming

Solution

Problem Understanding

This problem asks us to compute the number of distinct combinations of coins that can sum to a target amount. We are given an array coins, where each value represents a coin denomination, and an integer amount, which represents the target sum we want to form.

The important detail is that we are counting combinations, not permutations. This means the order of coins does not matter. For example, if amount = 5 and coins = [1,2,5], then 2 + 2 + 1 and 1 + 2 + 2 are considered the same combination, not different ones.

We are also told that we have an infinite supply of each coin denomination. This means any coin can be used as many times as needed.

The input consists of:

• amount, an integer target value
• coins, an array of unique coin denominations

The expected output is a single integer representing the number of unique combinations that sum exactly to amount. If no valid combination exists, we return 0.

The constraints provide useful guidance for selecting an efficient solution:

• amount <= 5000
• coins.length <= 300

A brute-force recursive solution that explores every possibility would quickly become infeasible because the number of combinations grows exponentially. Since amount is moderately large, this strongly suggests a dynamic programming approach.

Several important edge cases should be considered upfront.

If amount = 0, there is exactly one valid combination, choosing no coins at all. This often trips up implementations because many people mistakenly return 0.

If no combination can produce the target amount, such as amount = 3 and coins = [2], the answer must be 0.

If there is only one coin denomination, the algorithm must correctly determine whether repeated use of that coin can exactly reach the target.

The problem also guarantees that coin denominations are unique, which simplifies handling duplicate counting.

Approaches

Brute Force Approach

A straightforward solution is to recursively try every possible way to form the amount.

At each coin index, we have two choices:

1. Use the current coin again, since coins are unlimited.
2. Skip the current coin and move to the next denomination.

The recursion continues until:

• The remaining amount becomes 0, meaning we found a valid combination.
• The remaining amount becomes negative, meaning this path is invalid.
• We run out of coins before reaching 0.

This approach is correct because it systematically explores every valid possibility. However, many overlapping subproblems appear repeatedly. For example, different recursive paths may repeatedly ask, "How many ways can we make amount 3 using coins starting from index 2?"

Without memoization, the same calculations are recomputed many times, causing exponential growth in runtime.

Key Insight for an Optimal Solution

The key observation is that this problem has overlapping subproblems and optimal substructure, making it an excellent candidate for dynamic programming.

We can define a dynamic programming state where:

dp[x] = number of ways to make amount x.

Initially, there is exactly one way to make amount 0, by selecting no coins:

dp[0] = 1

We process coins one at a time. For each coin, we update all reachable amounts.

The crucial trick is the order of iteration.

We iterate through coins first, then amounts in increasing order. This ensures combinations are counted only once.

For example, when processing coin 2, we only extend combinations already built using earlier coins. This prevents counting reordered versions of the same combination.

Instead of storing a full 2D table, we can optimize space and use a 1D DP array.

Approaches Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(2^(amount + n))	O(amount)	Recursively explores all possibilities, excessive repeated computation
Optimal Dynamic Programming	O(amount × n)	O(amount)	Uses bottom-up DP to count combinations efficiently

Where n is the number of coin denominations.

Algorithm Walkthrough

Optimal Dynamic Programming Algorithm

1. Create a DP array of size amount + 1.

We use dp[i] to represent the number of ways to form amount i.

Initially, all values are 0 because we have not found any ways yet. 2. Set the base case.

We initialize:

dp[0] = 1

This represents the one valid way to create amount 0, choosing no coins. 3. Process each coin one at a time.

For every coin in coins, we iterate through all amounts from the coin value up to amount.

We start at the coin value because smaller amounts cannot include this coin. 4. Update the DP array.

For every amount current_amount, update:

dp[current_amount] += dp[current_amount - coin]

This means:

• dp[current_amount - coin] tells us how many ways exist to make the remaining value.
• By adding the current coin, all those ways become valid ways to make current_amount.

5. Continue until all coins are processed.

Since coins are processed sequentially, combinations are built without introducing duplicate orderings. 6. Return dp[amount].

This value contains the total number of unique combinations.

Why it works

The correctness comes from an important invariant:

After processing the first k coins, dp[x] stores the number of combinations to form amount x using only those k coins.

When we process a new coin, we extend previously valid combinations by adding this coin. Since each coin is processed only once in outer order, combinations are generated in a consistent order, preventing duplicates caused by rearrangement.

Python Solution

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 current_amount in range(coin, amount + 1):
                dp[current_amount] += dp[current_amount - coin]

        return dp[amount]

The implementation begins by creating a dynamic programming array called dp. Each index represents an amount, and the value at that index stores how many combinations can produce that amount.

The base case dp[0] = 1 is essential. It establishes that there is exactly one way to make amount 0.

The outer loop iterates through each coin denomination. This ordering is critical because it prevents counting different permutations of the same combination.

The inner loop starts from the coin value and moves upward to the target amount. For each amount, we update the number of ways by adding combinations that could form the remaining amount before adding the current coin.

Finally, the algorithm returns dp[amount], which contains the total number of valid combinations.

Go Solution

func change(amount int, coins []int) int {
	dp := make([]int, amount+1)
	dp[0] = 1

	for _, coin := range coins {
		for currentAmount := coin; currentAmount <= amount; currentAmount++ {
			dp[currentAmount] += dp[currentAmount-coin]
		}
	}

	return dp[amount]
}

The Go implementation follows the same logic as the Python solution. A slice is used instead of a list to store dynamic programming values.

Go initializes slices with zero values automatically, so no manual initialization is needed beyond setting dp[0] = 1.

There are no special concerns regarding integer overflow because the problem guarantees the result fits within a signed 32-bit integer. Go's int type is sufficient for this constraint.

Worked Examples

Example 1

Input:

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

Initial state:

Amount	0	1	2	3	4	5
dp	1	0	0	0	0	0

After processing coin 1

Amount	0	1	2	3	4	5
dp	1	1	1	1	1	1

There is exactly one way to form every amount using only 1s.

After processing coin 2

Amount	0	1	2	3	4	5
dp	1	1	2	2	3	3

Explanation:

• dp[2] = 2 → [1+1], [2]
• dp[3] = 2 → [1+1+1], [2+1]
• dp[5] = 3 → [1+1+1+1+1], [2+1+1+1], [2+2+1]

After processing coin 5

Amount	0	1	2	3	4	5
dp	1	1	2	2	3	4

The final combination [5] is added.

Answer:

4

Example 2

Input:

amount = 3
coins = [2]

Initial state:

Amount	0	1	2	3
dp	1	0	0	0

After processing coin 2:

Amount	0	1	2	3
dp	1	0	1	0

Amount 3 remains unreachable.

Answer:

0

Example 3

Input:

amount = 10
coins = [10]

Initial state:

Amount	0	1	2	3	4	5	6	7	8	9	10
dp	1	0	0	0	0	0	0	0	0	0	0

After processing coin 10:

Amount	0	1	2	3	4	5	6	7	8	9	10
dp	1	0	0	0	0	0	0	0	0	0	1

Answer:

1

Complexity Analysis

Measure	Complexity	Explanation
Time	O(amount × n)	We iterate through every coin and every amount once
Space	O(amount)	Only a single DP array of size amount + 1 is maintained

Where n is the number of coins.

The runtime is efficient because every (coin, amount) pair is processed exactly once. Since amount <= 5000 and coins.length <= 300, this comfortably fits within practical limits.

The space complexity remains linear because we avoid a 2D DP table and instead reuse a single one-dimensional array.

Test Cases

solution = Solution()

assert solution.change(5, [1, 2, 5]) == 4  # Provided example
assert solution.change(3, [2]) == 0  # No valid combination
assert solution.change(10, [10]) == 1  # Single exact coin

assert solution.change(0, [1, 2, 5]) == 1  # Zero amount edge case
assert solution.change(1, [2]) == 0  # Amount smaller than smallest coin
assert solution.change(2, [1, 2]) == 2  # [1+1], [2]

assert solution.change(4, [1, 2, 3]) == 4  # Multiple combinations
assert solution.change(5000, [1]) == 1  # Large amount with single coin
assert solution.change(11, [5, 7]) == 0  # Impossible target
assert solution.change(100, [1, 5, 10, 25]) == 242  # Larger realistic case

Test	Why
amount=5, [1,2,5]	Validates the standard example
amount=3, [2]	Ensures impossible sums return 0
amount=10, [10]	Tests single exact denomination
amount=0, [1,2,5]	Verifies base case behavior
amount=1, [2]	Tests amount smaller than any coin
amount=2, [1,2]	Confirms multiple valid combinations
amount=4, [1,2,3]	Checks mixed denomination counting
amount=5000, [1]	Stresses maximum amount constraint
amount=11, [5,7]	Verifies unreachable targets
amount=100, [1,5,10,25]	Tests larger DP computation

Edge Cases

One important edge case occurs when amount = 0. This case is easy to mishandle because some implementations mistakenly return 0. In reality, there is exactly one valid combination, selecting no coins. The implementation handles this correctly by initializing dp[0] = 1.

Another tricky case is when no valid combination exists. For example, amount = 3 and coins = [2] cannot produce the target. Since unreachable amounts never receive updates during dynamic programming, dp[3] remains 0, which is correctly returned.

A third important case occurs when there is only one coin denomination. For example, amount = 10 and coins = [10] should return 1, while amount = 9 and coins = [10] should return 0. The algorithm naturally handles both scenarios because updates only happen when the coin value fits within the current amount.

Another subtle edge case involves avoiding duplicate counting. For instance, 2 + 1 + 1 + 1 and 1 + 2 + 1 + 1 should count as the same combination. Processing coins in the outer loop guarantees that combinations are constructed in a fixed order, preventing permutation overcounting.