Coin Change II

Difficulty: Medium Source: NeetCode

Problem

You are given an integer amount and an array of integers coins representing coin denominations. Return the number of combinations (order doesn’t matter) that make up the amount. If no combination is possible, return 0.

Example 1: Input: amount = 5, coins = [1, 2, 5] Output: 4 Explanation: 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

Constraints:

• 1 <= coins.length <= 300
• 1 <= coins[i] <= 5000
• 0 <= amount <= 5000

Prerequisites

Before attempting this problem, you should be comfortable with:

• Coin Change I (322) — minimum coins version
• Unbounded Knapsack — each item can be used unlimited times
• Combinations vs Permutations — order doesn’t matter here

1. Brute Force / Recursive

Intuition

For each coin, decide how many times to use it (0, 1, 2, …). This naturally avoids counting permutations because we process coins one at a time — once we move past a coin, we never revisit it. Recurse through each coin with a remaining amount.

Algorithm

1. Define dfs(i, remaining) = number of ways to make remaining using coins[i:].
2. Base case: remaining == 0 → return 1 (found a valid combination).
3. Base case: remaining < 0 or i == len(coins) → return 0.
4. Return dfs(i, remaining - coins[i]) + dfs(i + 1, remaining).
   • First term: use coins[i] again (unbounded).
   • Second term: skip to next coin.

Solution

def change(amount, coins):
    def dfs(i, remaining):
        if remaining == 0:
            return 1
        if remaining < 0 or i == len(coins):
            return 0
        return dfs(i, remaining - coins[i]) + dfs(i + 1, remaining)

    return dfs(0, amount)


print(change(5, [1, 2, 5]))  # 4
print(change(3, [2]))        # 0
print(change(10, [10]))      # 1

Complexity

• Time: O(amount^len(coins)) — very slow without memoization
• Space: O(amount) — recursion depth

2. Bottom-Up DP (Tabulation)

Intuition

Build a 1D dp array where dp[j] = number of ways to make amount j. Initialise dp[0] = 1 (one way to make 0: use no coins). For each coin, iterate amounts from coin to amount and add dp[j - coin] to dp[j]. The outer loop is over coins (not amounts) — this is critical! It ensures we count combinations, not permutations. If we put amounts on the outside, we’d count [1,2] and [2,1] as separate.

Algorithm

1. dp = [0] * (amount + 1), set dp[0] = 1.
2. For each coin in coins:
   • For j from coin to amount:
     • dp[j] += dp[j - coin]
3. Return dp[amount].

Solution

def change(amount, coins):
    dp = [0] * (amount + 1)
    dp[0] = 1

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

    return dp[amount]


print(change(5, [1, 2, 5]))  # 4
print(change(3, [2]))        # 0
print(change(10, [10]))      # 1
print(change(0, [1, 2, 5]))  # 1  (one way to make 0)


# 2D DP version (easier to understand the transition)
def change_2d(amount, coins):
    m = len(coins)
    dp = [[0] * (amount + 1) for _ in range(m + 1)]
    for i in range(m + 1):
        dp[i][0] = 1  # one way to make 0

    for i in range(1, m + 1):
        for j in range(amount + 1):
            dp[i][j] = dp[i - 1][j]  # don't use coins[i-1]
            if j >= coins[i - 1]:
                dp[i][j] += dp[i][j - coins[i - 1]]  # use coins[i-1] again

    return dp[m][amount]


print(change_2d(5, [1, 2, 5]))  # 4

Complexity

• Time: O(len(coins) * amount)
• Space: O(amount) for 1D; O(len(coins) * amount) for 2D

Common Pitfalls

Swapping the loop order. If you loop over amounts on the outside and coins on the inside, you count permutations (ordered sequences). Coin Change II wants combinations (unordered). Always loop coins first, amounts second.

Not initialising dp[0] = 1. The base case “one way to make 0” is what seeds all the other values. If it’s 0, nothing propagates and you’ll always get 0.

Confusing this with Coin Change I. In Coin Change I you track the minimum number of coins; here you track the count of combinations. The transition is addition (+=) not min.