LeetEye LeetEye
Medium 2D Dynamic Programming ~5 min

Coin Change II

2d-dp coin-change-ii

Problem

You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money.

Return the number of combinations that make up that amount. If that amount of money cannot be made up by any combination of the coins, return 0.

You may assume that you have an infinite number of each kind of coin.

Examples

Example 1
Input: amount = 5, coins = [1, 2, 5]
Output: 4
5=5, 5=2+2+1, 5=2+1+1+1, 5=1+1+1+1+1
Example 2
Input: amount = 3, coins = [2]
Output: 0
Example 3
Input: amount = 10, coins = [10]
Output: 1
Key Insight

Process coins one at a time to avoid counting permutations.

Unbounded knapsack for counting. Outer loop on coins (not amounts) ensures combinations, not permutations. dp[j] += dp[j - coin].

How to Approach This Problem

Pattern Recognition: When you see keywords like coin change ii 2d-dp, think 2D Dynamic Programming.

Step-by-Step Reasoning

1 Why is this different from "ways to reach amount"?
Answer: All of above
Order matters in permutations (stairs), not in combinations (coins).
2 To count combinations only:
Answer: Process coins first, amounts second (combinations)
Process each coin completely before moving to next. Ensures each combination counted once.
3 Outer loop on coins ensures:
Answer: Combinations like [1,2] and [2,1] counted once
By fixing coin order (coin1, then coin2, ...), we only count [coin1, coin1, coin2], never [coin2, coin1, coin1].
4 dp[j] after considering coin:
Answer: dp[j] + dp[j - coin]
Ways without this coin + ways using at least one of this coin.
5 dp[0] should be:
Answer: 1
One way to make amount 0: use no coins.

Solution

def change(amount: int, coins: List[int]) -> int:
    dp = [0] * (amount + 1)
    dp[0] = 1  # One way to make 0: use nothing
    
    # Outer loop on coins = combinations (not permutations)
    for coin in coins:
        for j in range(coin, amount + 1):
            dp[j] += dp[j - coin]
    
    return dp[amount]

Complexity Analysis

Time O(amount × coins)
Space O(amount)

Master This Pattern

Build intuition with interactive MCQs. Practice 2D Dynamic Programming problems in the LeetEye app.

Download LeetEye Free
Practice in LeetEye