Skip to main content
CodePeetCodePeet
CodePeet 250

Coin Change II

MEDIUMProblemSolveExternal Links

Description

You are given an integer array coins where each element represents a coin of a particular denomination, and an integer amount representing a total sum of money.

Return the number of different combinations that make up the given amount. If no combination of coins can produce that amount, return 0.

You may assume that you have an infinite supply of each coin denomination. Two combinations are considered different only if they differ in the count of at least one denomination used — the order of coins does not matter.

For example, using coins [1, 2] to make amount 3, the combination [1, 2] is the same as [2, 1] — they count as one combination, not two.

Examples

Example 1

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

Output: 4

Explanation: There are four distinct combinations that sum to 5:

  • 5 = 5 (one coin of value 5)
  • 5 = 2 + 2 + 1 (two coins of value 2, one coin of value 1)
  • 5 = 2 + 1 + 1 + 1 (one coin of value 2, three coins of value 1)
  • 5 = 1 + 1 + 1 + 1 + 1 (five coins of value 1)

Notice that the order does not matter — [2, 2, 1] and [1, 2, 2] are the same combination.

Example 2

Input: amount = 3, coins = [2]

Output: 0

Explanation: With only coins of denomination 2, we can make sums 0, 2, 4, 6, ... but never an odd number like 3. There is no way to form amount 3, so we return 0.

Example 3

Input: amount = 10, coins = [10]

Output: 1

Explanation: The only way to make amount 10 with coins of denomination 10 is to use exactly one coin. There is exactly 1 combination.

Constraints

  • 1 ≤ coins.length ≤ 300
  • 1 ≤ coins[i] ≤ 5000
  • All the values of coins are unique
  • 0 ≤ amount ≤ 5000
  • The answer is guaranteed to fit into a signed 32-bit integer

Editorial

Brute Force

Intuition

The most natural way to think about this problem is through choices. Imagine you are standing in front of a pile of coins, and for each coin denomination you have a decision to make: do I include this coin in my current combination, or do I skip it entirely?

If you decide to include a coin, the remaining amount you need to form decreases by that coin's value — and since you have an infinite supply, you can pick the same coin again. If you skip the coin, you move on to the next denomination and never look back.

This gives us a recursive strategy: at each step, either take the current coin (and stay at the same coin for potential reuse) or skip it (and move to the next denomination). We count all the paths through this decision tree that successfully reach a remaining amount of zero.

Step-by-Step Explanation

Let's trace through with amount = 5, coins = [1, 2, 5]. We'll use a recursive function count(coinIndex, remaining) that returns the number of ways to make remaining using coins from index coinIndex onward.

Step 1: Start with count(0, 5) — we have all coins available and need to make 5.

Step 2: At coin index 0 (coin=1), we choose to include coin 1. Remaining becomes 5-1=4. Call count(0, 4).

Step 3: This recursion continues including coin 1 repeatedly: count(0,3) → count(0,2) → count(0,1) → count(0,0). When remaining=0, we found one valid combination: [1,1,1,1,1]. Return 1.

Step 4: Backtrack to count(0,1). Now try skipping coin 1 → call count(1, 1). At coin index 1 (coin=2), remaining=1. Since 2>1, we cannot include coin 2. Skip → count(2, 1). At coin index 2 (coin=5), 5>1, skip → count(3, 1). No more coins, remaining≠0, return 0.

Step 5: Backtrack further to count(0,2). After using coin 1 repeatedly has been explored, try skipping coin 1 → count(1, 2). Include coin 2: remaining=0 → found [1,1,1,2] path that reaches here. This eventually discovers combination [2,2,1] and [2,1,1,1].

Step 6: The recursion tree branches exponentially, exploring every possible way to combine coins. Many subproblems like count(0, 3) are computed multiple times across different branches.

Result: After exploring the entire recursion tree, we find 4 total combinations.

Recursive Exploration of Coin Combinations — Watch how the recursion branches at each step: include the current coin (go left) or skip to the next denomination (go right). Leaves that reach amount=0 are valid combinations.

Algorithm

  1. Define a recursive function count(coinIndex, remaining) that returns the number of ways to form remaining using coins from index coinIndex onward.
  2. Base cases:
    • If remaining == 0, return 1 (found a valid combination)
    • If remaining < 0 or coinIndex >= coins.length, return 0 (invalid path)
  3. Recursive case: Return the sum of:
    • count(coinIndex, remaining - coins[coinIndex]) — include current coin (stay at same index for reuse)
    • count(coinIndex + 1, remaining) — skip current coin (move to next denomination)
  4. The initial call is count(0, amount).

Code

class Solution {
public:
    int change(int amount, vector<int>& coins) {
        return countWays(coins, 0, amount);
    }
    
    int countWays(vector<int>& coins, int index, int remaining) {
        if (remaining == 0) return 1;
        if (remaining < 0 || index >= coins.size()) return 0;
        
        // Include current coin (can reuse) + Skip current coin
        return countWays(coins, index, remaining - coins[index])
             + countWays(coins, index + 1, remaining);
    }
};
class Solution:
    def change(self, amount: int, coins: list[int]) -> int:
        def count_ways(index: int, remaining: int) -> int:
            if remaining == 0:
                return 1
            if remaining < 0 or index >= len(coins):
                return 0
            
            # Include current coin (can reuse) + Skip current coin
            return count_ways(index, remaining - coins[index]) \
                 + count_ways(index + 1, remaining)
        
        return count_ways(0, amount)
class Solution {
    public int change(int amount, int[] coins) {
        return countWays(coins, 0, amount);
    }
    
    private int countWays(int[] coins, int index, int remaining) {
        if (remaining == 0) return 1;
        if (remaining < 0 || index >= coins.length) return 0;
        
        // Include current coin (can reuse) + Skip current coin
        return countWays(coins, index, remaining - coins[index])
             + countWays(coins, index + 1, remaining);
    }
}

Complexity Analysis

Time Complexity: O(2^amount)

In the worst case, the recursion tree branches into two at every level, and the tree can be as deep as amount (when repeatedly picking the smallest coin of value 1). This leads to exponential time as we explore every possible combination without remembering results.

Space Complexity: O(amount)

The maximum depth of the recursion stack is amount (when we pick coin=1 repeatedly, reducing remaining by 1 each time). Each stack frame uses O(1) space, so total stack space is O(amount).

Why This Approach Is Not Efficient

The brute force recursion has exponential time complexity O(2^amount). With amount up to 5000 and up to 300 coin denominations, this is hopelessly slow — the recursion tree would have billions of nodes.

The root cause is overlapping subproblems. The same (coinIndex, remaining) pair is computed over and over across different branches of the tree. For example, count(1, 3) might be called from count(0, 4) (after including coin 1 once) and also from count(0, 3) (after skipping coin 1), and each call recomputes the entire subtree.

Key insight: if we store the result of each unique (coinIndex, remaining) pair the first time we compute it, we can look it up in O(1) on subsequent calls. This transforms the problem from exponential to polynomial — the total number of unique subproblems is at most coins.length × (amount + 1).

Better Approach - 2D Dynamic Programming (Tabulation)

Intuition

Instead of the top-down recursion with memoization, we can build our answer bottom-up using a 2D table. The idea is to fill in a table dp[i][j] where i represents the number of coin denominations we are allowed to use (first i coins), and j represents the target amount.

dp[i][j] answers the question: "How many ways can I form amount j using only the first i coin denominations?"

We fill this table row by row. For each new coin we introduce, we decide for every target amount: the ways without using this coin (carried from the row above) plus the ways that include at least one of this coin (looked up in the same row at a smaller amount).

Think of it like a shopkeeper gradually stocking new types of coins. First the shop only has coin 1. Then coin 2 is added. Then coin 5. For each new coin added, we recalculate how many ways customers can pay for every amount from 0 to the target.

Step-by-Step Explanation

Let's trace with amount = 5, coins = [1, 2, 5]. We build a 2D table dp of size (coins.length+1) × (amount+1) = 4 × 6.

Step 1: Initialize the table. dp[0][0] = 1 (there is exactly one way to make amount 0 with 0 coins: use nothing). For all j > 0, dp[0][j] = 0 (impossible to make a positive amount with no coins).

Step 2: Fill row i=1 (using only coin 1). For j=0: dp[1][0] = 1 (one way to make 0). For j=1: dp[1][1] = dp[0][1] + dp[1][0] = 0 + 1 = 1. We can make 1 using [1].

Step 3: Continue row i=1. j=2: dp[1][2] = dp[0][2] + dp[1][1] = 0 + 1 = 1 → [1,1]. j=3: dp[1][3] = 0 + 1 = 1 → [1,1,1]. j=4: 0 + 1 = 1 → [1,1,1,1]. j=5: 0 + 1 = 1 → [1,1,1,1,1]. With only coin 1, there's exactly one way to make any amount.

Step 4: Fill row i=2 (using coins 1 and 2). j=0: dp[2][0] = 1. j=1: dp[2][1] = dp[1][1] + dp[2][-1] = 1 + 0 = 1 (coin 2 is too large for amount 1).

Step 5: Continue row i=2. j=2: dp[2][2] = dp[1][2] + dp[2][0] = 1 + 1 = 2. Two ways: [1,1] and [2]. j=3: dp[2][3] = dp[1][3] + dp[2][1] = 1 + 1 = 2. Two ways: [1,1,1] and [1,2].

Step 6: Continue row i=2. j=4: dp[2][4] = dp[1][4] + dp[2][2] = 1 + 2 = 3. Three ways: [1,1,1,1], [1,1,2], [2,2]. j=5: dp[2][5] = dp[1][5] + dp[2][3] = 1 + 2 = 3. Three ways: [1,1,1,1,1], [1,1,1,2], [1,2,2].

Step 7: Fill row i=3 (using coins 1, 2, and 5). j=0 through j=4: dp[3][j] = dp[2][j] + 0 (coin 5 is too large for amounts < 5, so no new ways added).

Step 8: j=5: dp[3][5] = dp[2][5] + dp[3][0] = 3 + 1 = 4. The new combination is [5]. Final answer: dp[3][5] = 4.

2D DP Table — Building Coin Combinations Bottom-Up — Watch how the DP table fills cell by cell. Each cell dp[i][j] counts ways to form amount j using the first i coin types. The value comes from the cell directly above (exclude coin) plus a cell to the left in the same row (include coin).

Algorithm

  1. Create a 2D table dp of size (n+1) × (amount+1), initialized to 0, where n = coins.length.
  2. Set dp[0][0] = 1 (one way to make 0 with no coins).
  3. For each coin index i from 1 to n:
    • For each target j from 0 to amount:
      • dp[i][j] = dp[i-1][j] (ways without using coin i)
      • If j >= coins[i-1]: add dp[i][j - coins[i-1]] (ways that include at least one coin i)
  4. Return dp[n][amount].

Code

class Solution {
public:
    int change(int amount, vector<int>& coins) {
        int n = coins.size();
        vector<vector<int>> dp(n + 1, vector<int>(amount + 1, 0));
        dp[0][0] = 1;
        
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j <= amount; j++) {
                dp[i][j] = dp[i - 1][j];
                if (j >= coins[i - 1]) {
                    dp[i][j] += dp[i][j - coins[i - 1]];
                }
            }
        }
        
        return dp[n][amount];
    }
};
class Solution:
    def change(self, amount: int, coins: list[int]) -> int:
        n = len(coins)
        dp = [[0] * (amount + 1) for _ in range(n + 1)]
        dp[0][0] = 1
        
        for i in range(1, n + 1):
            for j in range(amount + 1):
                dp[i][j] = dp[i - 1][j]
                if j >= coins[i - 1]:
                    dp[i][j] += dp[i][j - coins[i - 1]]
        
        return dp[n][amount]
class Solution {
    public int change(int amount, int[] coins) {
        int n = coins.length;
        int[][] dp = new int[n + 1][amount + 1];
        dp[0][0] = 1;
        
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j <= amount; j++) {
                dp[i][j] = dp[i - 1][j];
                if (j >= coins[i - 1]) {
                    dp[i][j] += dp[i][j - coins[i - 1]];
                }
            }
        }
        
        return dp[n][amount];
    }
}

Complexity Analysis

Time Complexity: O(n × amount)

We fill a table with n rows (one per coin) and amount + 1 columns. Each cell is computed in O(1) time using the recurrence relation. With n up to 300 and amount up to 5000, this gives at most 1.5 × 10^6 operations — well within time limits.

Space Complexity: O(n × amount)

The 2D DP table stores (n+1) × (amount+1) integers. For n=300 and amount=5000, this is about 1.5 million integers (~6 MB), which is acceptable but can be optimized.

Why This Approach Is Not Efficient

The 2D DP solution has optimal time complexity O(n × amount) — we cannot do better because we must consider every coin for every amount. However, the space complexity O(n × amount) is wasteful.

Look at the recurrence: dp[i][j] = dp[i-1][j] + dp[i][j - coins[i-1]]. Each cell depends only on the row directly above (dp[i-1][j]) and the current row to the left (dp[i][j - coins[i-1]]). We never look back more than one row.

This means we only need two rows at a time — or even better, just a single 1D array that we update in place. By processing columns left to right for each coin, the current row naturally contains both the "previous row" values (not yet overwritten) and the "current row" values (already updated to the left).

This insight reduces space from O(n × amount) to O(amount).

Optimal Approach - Space-Optimized 1D DP

Intuition

We compress the entire 2D table into a single 1D array dp of size amount + 1. The key insight is how the update order works:

We process coins one by one (outer loop). For each coin, we sweep through amounts from coin_value up to amount (inner loop, left to right). At each position j, we add dp[j - coin_value] to dp[j].

Why does this work? Before we start processing a coin, dp[j] holds the number of ways using all previous coins (equivalent to the row above in the 2D table). As we sweep left to right, positions to the left of j have already been updated for the current coin, so dp[j - coin_value] already includes the current coin — which is exactly what we need for the "include this coin" case.

Think of it like this: the 1D array acts as a running scoreboard. As each new coin type is introduced, the scoreboard updates left to right, and each slot accumulates the new ways that the latest coin enables.

Critically, processing amounts from left to right (small to large) allows unlimited reuse of the same coin (unbounded knapsack). If we processed right to left, each coin could only be used once (0/1 knapsack). The direction of the inner loop is what distinguishes these two classic DP patterns.

Step-by-Step Explanation

Let's trace with amount = 5, coins = [1, 2, 5]. Our 1D array dp has 6 slots (indices 0 through 5).

Step 1: Initialize dp = [1, 0, 0, 0, 0, 0]. dp[0]=1 means there is one way to make amount 0 (use no coins). All other slots start at 0.

Step 2: Process coin = 1. Start inner loop from j=1. dp[1] += dp[1-1] = dp[0] = 1 → dp[1] = 0 + 1 = 1.

Step 3: Continue with coin = 1. dp[2] += dp[1] = 1 → dp[2] = 1. dp[3] += dp[2] = 1 → dp[3] = 1. dp[4] += dp[3] = 1 → dp[4] = 1. dp[5] += dp[4] = 1 → dp[5] = 1. Array: [1, 1, 1, 1, 1, 1].

Step 4: Process coin = 2. Start from j=2. dp[2] += dp[0] = 1 → dp[2] = 1 + 1 = 2.

Step 5: Continue with coin = 2. dp[3] += dp[1] = 1 → dp[3] = 1 + 1 = 2. dp[4] += dp[2] = 2 → dp[4] = 1 + 2 = 3. dp[5] += dp[3] = 2 → dp[5] = 1 + 2 = 3. Array: [1, 1, 2, 2, 3, 3].

Step 6: Process coin = 5. Start from j=5. dp[5] += dp[0] = 1 → dp[5] = 3 + 1 = 4. Array: [1, 1, 2, 2, 3, 4].

Result: dp[5] = 4. There are 4 combinations to make amount 5.

1D DP Array — Space-Optimized Coin Change — Watch how a single array is updated coin by coin. For each coin, we sweep left to right, adding the ways from a smaller subproblem. The left-to-right order allows unlimited reuse of each coin.

Algorithm

  1. Create a 1D array dp of size amount + 1, initialized to 0.
  2. Set dp[0] = 1 (one way to make amount 0).
  3. For each coin in coins:
    • For each amount j from coin to amount:
      • dp[j] += dp[j - coin]
  4. Return dp[amount].

The outer loop iterates over coins (not amounts) to ensure we count combinations, not permutations. If we swapped the loops (amounts outer, coins inner), we would count different orderings as separate ways, which is a different problem.

Code

class Solution {
public:
    int change(int amount, vector<int>& coins) {
        vector<int> dp(amount + 1, 0);
        dp[0] = 1;
        
        for (int coin : coins) {
            for (int j = coin; j <= amount; j++) {
                dp[j] += dp[j - coin];
            }
        }
        
        return dp[amount];
    }
};
class Solution:
    def change(self, amount: int, coins: list[int]) -> int:
        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]
class Solution {
    public int change(int amount, int[] coins) {
        int[] dp = new int[amount + 1];
        dp[0] = 1;
        
        for (int coin : coins) {
            for (int j = coin; j <= amount; j++) {
                dp[j] += dp[j - coin];
            }
        }
        
        return dp[amount];
    }
}

Complexity Analysis

Time Complexity: O(n × amount)

The outer loop runs n times (once per coin), and for each coin the inner loop runs up to amount times. Each iteration does a constant-time addition. Total: O(n × amount). This is the same as the 2D approach — we did not sacrifice time for space.

Space Complexity: O(amount)

We use a single 1D array of size amount + 1. For amount up to 5000, this is just 5001 integers (~20 KB). This is a significant improvement over the O(n × amount) space of the 2D table, which is especially impactful when n (number of coin types) is large.