Skip to main content
CodePeetCodePeet
CodePeet 150

Coin Change

MEDIUMProblemSolveExternal Links

Description

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

Your task is to determine the fewest number of coins needed to make up exactly that amount. You have an unlimited supply of each coin denomination.

If it is impossible to form the given amount using any combination of the available coins, return -1.

If the amount is 0, no coins are needed, so return 0.

Examples

Example 1

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

Output: 3

Explanation: The optimal way to make 11 is to use two coins of denomination 5 and one coin of denomination 1: 5 + 5 + 1 = 11. This uses only 3 coins. Other combinations like 2 + 2 + 2 + 5 = 11 use 4 coins, and 1 + 1 + ... + 1 = 11 uses 11 coins — so 3 is the minimum.

Example 2

Input: coins = [2], amount = 3

Output: -1

Explanation: There is only one denomination available: 2. No matter how many coins of value 2 we use, we can only form even numbers (2, 4, 6, ...). Since 3 is odd, it is impossible to reach exactly 3, so we return -1.

Example 3

Input: coins = [1], amount = 0

Output: 0

Explanation: When the target amount is 0, we already have the exact sum without using any coins. Zero coins are needed.

Constraints

  • 1 ≤ coins.length ≤ 12
  • 1 ≤ coins[i] ≤ 2^31 - 1
  • 0 ≤ amount ≤ 10^4

Editorial

Brute Force

Intuition

The most straightforward way to think about this problem is: try every possible combination of coins and pick the one that uses the fewest coins.

Imagine you are standing in front of a vending machine that only accepts exact change. You have piles of coins of different values in your pocket. You could try putting in one coin at a time, exploring all possible sequences — first try using the largest coin, then the next, then the next — and track which sequence reaches the target amount with the least number of coins.

Formally, for each coin denomination, we have two choices at every step:

  1. Use this coin — subtract its value from the remaining amount and keep this coin type available for future use (since supply is infinite).
  2. Skip this coin — move on to the next denomination.

This naturally leads to a recursive exploration of all possibilities. We try each coin denomination, and for each one we recursively solve the smaller subproblem of making the remaining amount. We take the minimum across all options.

Step-by-Step Explanation

Let's trace through with coins = [1, 2, 5], amount = 5 (using a smaller amount for clarity):

Step 1: Start with amount = 5. Try coin 5: remaining = 5 - 5 = 0. That took 1 coin. Result: 1.

Step 2: Backtrack. Try coin 2: remaining = 5 - 2 = 3. Need to solve for amount = 3.

Step 3: For amount = 3, try coin 2: remaining = 3 - 2 = 1. Need to solve for amount = 1.

Step 4: For amount = 1, try coin 2: remaining = 1 - 2 = -1. Negative — this path is invalid.

Step 5: For amount = 1, try coin 1: remaining = 1 - 1 = 0. That took 1 coin. So amount = 1 needs 1 coin.

Step 6: Back to amount = 3: using coin 2 gave us 1 + 1 = 2 coins. Try coin 1: remaining = 3 - 1 = 2, then 2 - 1 = 1, then 1 - 1 = 0. That's 3 coins. Minimum for amount = 3 is 2 coins.

Step 7: Back to amount = 5: using coin 2 gave us 1 + 2 = 3 coins. Try coin 1: that would take 5 coins.

Step 8: Compare all paths: coin 5 → 1 coin, coin 2 → 3 coins, coin 1 → 5 coins. Minimum is 1.

Result: The answer is 1 coin (using a single coin of denomination 5).

Brute Force Recursion — Exploring All Coin Choices — Watch how the recursive approach explores every possible coin choice, branching at each step, and backtracks when a path fails or completes.

Algorithm

  1. Define a recursive function solve(amount) that returns the minimum coins needed to make amount.
  2. Base case: If amount == 0, return 0 (no coins needed).
  3. Base case: If amount < 0, return infinity (this path is invalid).
  4. For each coin denomination c in the coins array:
    • Recursively call solve(amount - c) to get the result if we use coin c.
    • Add 1 to account for using this coin.
  5. Return the minimum across all coin choices.
  6. If the minimum is still infinity, return -1 (impossible to form the amount).

Code

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        int result = solve(coins, amount);
        return result == INT_MAX ? -1 : result;
    }
    
    int solve(vector<int>& coins, int amount) {
        if (amount == 0) return 0;
        if (amount < 0) return INT_MAX;
        
        int minCoins = INT_MAX;
        for (int coin : coins) {
            int sub = solve(coins, amount - coin);
            if (sub != INT_MAX) {
                minCoins = min(minCoins, sub + 1);
            }
        }
        return minCoins;
    }
};
class Solution:
    def coinChange(self, coins: list[int], amount: int) -> int:
        def solve(remaining):
            if remaining == 0:
                return 0
            if remaining < 0:
                return float('inf')
            
            min_coins = float('inf')
            for coin in coins:
                sub = solve(remaining - coin)
                min_coins = min(min_coins, sub + 1)
            return min_coins
        
        result = solve(amount)
        return result if result != float('inf') else -1
class Solution {
    public int coinChange(int[] coins, int amount) {
        int result = solve(coins, amount);
        return result == Integer.MAX_VALUE ? -1 : result;
    }
    
    private int solve(int[] coins, int amount) {
        if (amount == 0) return 0;
        if (amount < 0) return Integer.MAX_VALUE;
        
        int minCoins = Integer.MAX_VALUE;
        for (int coin : coins) {
            int sub = solve(coins, amount - coin);
            if (sub != Integer.MAX_VALUE) {
                minCoins = Math.min(minCoins, sub + 1);
            }
        }
        return minCoins;
    }
}

Complexity Analysis

Time Complexity: O(n^amount)

In the worst case, for each of the amount levels of recursion, we branch into n choices (one per coin). This creates an exponential number of recursive calls. For example, with coins = [1, 2, 5] and amount = 11, the recursion tree can have up to 3^11 nodes.

Space Complexity: O(amount)

The maximum depth of the recursion stack is amount (in the worst case, we subtract 1 at each level when using the smallest coin). Each recursive call uses O(1) extra space, so the total stack space is O(amount).

Why This Approach Is Not Efficient

The brute force recursion has exponential time complexity because it recomputes the same subproblems over and over. For instance, solve(3) might be called from solve(5) via coin 2, and also from solve(4) via coin 1 — and each of those calls spawns its own subtree.

With amount up to 10^4 and up to 12 coin denominations, the number of recursive calls can be astronomical — far beyond what any computer can handle in a reasonable time.

The key observation is that the result of solve(x) depends only on x, not on how we arrived at x. Once we know the minimum coins for a given remaining amount, we should store and reuse that answer. This is the insight that leads to dynamic programming.

Better Approach - Memoized Recursion (Top-Down DP)

Intuition

The brute force recalculates solve(x) for the same value of x many times. We can fix this by storing the result the first time we compute it, and simply looking it up on subsequent calls. This technique is called memoization.

Think of it like taking notes during an exam. If you solved a particular sub-calculation once, you write down the answer. The next time you need that same sub-calculation, you just read your note instead of redoing the work.

We use an array (or dictionary) of size amount + 1. Before computing solve(x), we check if we already have the answer stored. If yes, return it immediately. If no, compute it, store it, and return it. This eliminates all redundant work.

Step-by-Step Explanation

Let's trace with coins = [1, 2, 5], amount = 5:

Step 1: Initialize memo array of size 6 (indices 0 through 5), all set to -1 (uncomputed). Base: memo[0] = 0.

Step 2: Call solve(5). Not in memo. Try coin 5: solve(0) = 0 → 0 + 1 = 1 coin.

Step 3: Try coin 2: solve(3). Not in memo. For solve(3): try coin 2 → solve(1). Try coin 1 → solve(0) = 0 → 1 coin. memo[1] = 1.

Step 4: Back in solve(3): solve(1) = 1 → via coin 2 that's 1 + 1 = 2. Try coin 1 → solve(2). For solve(2): coin 2 → solve(0) = 0 → 1 coin. memo[2] = 1.

Step 5: Back in solve(3): solve(2) = 1 → via coin 1 that's 1 + 1 = 2. Try coin 5 → solve(-2) invalid. Minimum for solve(3) is min(2, 2) = 2. memo[3] = 2.

Step 6: Back in solve(5): via coin 2 that's 2 + 1 = 3. Try coin 1 → solve(4). For solve(4): coin 5 invalid, coin 2 → solve(2) = 1 (from memo!) → 2 coins. coin 1 → solve(3) = 2 (from memo!) → 3 coins. memo[4] = 2.

Step 7: solve(5): via coin 1 that's 2 + 1 = 3. Minimum across all: min(1, 3, 3) = 1. memo[5] = 1.

Result: 1 coin. Notice how solve(2) and solve(3) were looked up from memo instead of recomputed.

Memoized Recursion — Pruning Redundant Calls — Watch how memoization stores results of subproblems and instantly returns cached answers when the same subproblem is encountered again, avoiding redundant computation.

Algorithm

  1. Create a memo array of size amount + 1, initialized to -1 (uncomputed).
  2. Set memo[0] = 0 (base case: zero coins needed for amount 0).
  3. Define solve(remaining):
    • If remaining < 0, return infinity.
    • If memo[remaining] != -1, return memo[remaining] (cached result).
    • For each coin c, compute 1 + solve(remaining - c).
    • Store the minimum in memo[remaining] and return it.
  4. Call solve(amount). If the result is infinity, return -1.

Code

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        vector<int> memo(amount + 1, -1);
        memo[0] = 0;
        int result = solve(coins, amount, memo);
        return result == INT_MAX ? -1 : result;
    }
    
    int solve(vector<int>& coins, int amount, vector<int>& memo) {
        if (amount < 0) return INT_MAX;
        if (memo[amount] != -1) return memo[amount];
        
        int minCoins = INT_MAX;
        for (int coin : coins) {
            int sub = solve(coins, amount - coin, memo);
            if (sub != INT_MAX) {
                minCoins = min(minCoins, sub + 1);
            }
        }
        memo[amount] = minCoins;
        return minCoins;
    }
};
class Solution:
    def coinChange(self, coins: list[int], amount: int) -> int:
        memo = [-1] * (amount + 1)
        memo[0] = 0
        
        def solve(remaining):
            if remaining < 0:
                return float('inf')
            if memo[remaining] != -1:
                return memo[remaining]
            
            min_coins = float('inf')
            for coin in coins:
                sub = solve(remaining - coin)
                min_coins = min(min_coins, sub + 1)
            
            memo[remaining] = min_coins
            return min_coins
        
        result = solve(amount)
        return result if result != float('inf') else -1
class Solution {
    public int coinChange(int[] coins, int amount) {
        int[] memo = new int[amount + 1];
        Arrays.fill(memo, -1);
        memo[0] = 0;
        int result = solve(coins, amount, memo);
        return result == Integer.MAX_VALUE ? -1 : result;
    }
    
    private int solve(int[] coins, int amount, int[] memo) {
        if (amount < 0) return Integer.MAX_VALUE;
        if (memo[amount] != -1) return memo[amount];
        
        int minCoins = Integer.MAX_VALUE;
        for (int coin : coins) {
            int sub = solve(coins, amount - coin, memo);
            if (sub != Integer.MAX_VALUE) {
                minCoins = Math.min(minCoins, sub + 1);
            }
        }
        memo[amount] = minCoins;
        return minCoins;
    }
}

Complexity Analysis

Time Complexity: O(n × amount)

There are amount + 1 unique subproblems (one for each value from 0 to amount). Each subproblem tries all n coin denominations. With memoization, each subproblem is solved at most once, so the total work is O(n × amount).

Space Complexity: O(amount)

The memo array stores one result per amount value, taking O(amount) space. The recursion stack depth is also at most O(amount) in the worst case (using the smallest coin denomination repeatedly).

Why This Approach Is Not Efficient

The memoized recursion achieves the optimal O(n × amount) time complexity, which is the same as the bottom-up DP approach. However, it still has a practical disadvantage: the recursion stack.

With amount up to 10^4 and the smallest coin being 1, the recursion can go 10^4 levels deep. This risks stack overflow in languages with limited default stack sizes (like Python's default recursion limit of ~1000).

Additionally, recursive calls have overhead (function call frames, return address management) that iterative solutions avoid. A bottom-up approach fills the DP table iteratively, eliminating recursion entirely and often running faster in practice due to better cache locality.

Optimal Approach - Bottom-Up Dynamic Programming

Intuition

Instead of solving top-down (from amount down to 0) and caching results, we can build up the solution bottom-up: start from amount 0 and work our way up to the target.

Imagine you are climbing a staircase where each step represents a monetary amount from 0 to amount. You start at step 0 (base case: 0 coins needed). For each subsequent step, you look at all the steps you could have jumped from (one jump per coin denomination) and pick the one that got there in the fewest jumps, then add 1.

We create an array dp of size amount + 1, where dp[i] represents the minimum number of coins needed to make amount i. We initialize dp[0] = 0 and everything else to a large value (representing "not yet achievable"). Then for each amount from 1 to amount, we try every coin and update accordingly.

The recurrence relation is:

dp[i] = min(dp[i], dp[i - coin] + 1) for every coin where i - coin ≥ 0.

Step-by-Step Explanation

Let's trace with coins = [1, 2, 5], amount = 7:

Step 1: Initialize dp = [0, ∞, ∞, ∞, ∞, ∞, ∞, ∞]. dp[0] = 0 (base case).

Step 2: Fill dp[1]. Try coin 1: dp[1-1] + 1 = dp[0] + 1 = 1. Try coin 2: 1-2 < 0 (skip). Try coin 5: 1-5 < 0 (skip). dp[1] = 1.

Step 3: Fill dp[2]. Try coin 1: dp[1] + 1 = 2. Try coin 2: dp[0] + 1 = 1. Try coin 5: skip. dp[2] = min(2, 1) = 1.

Step 4: Fill dp[3]. Try coin 1: dp[2] + 1 = 2. Try coin 2: dp[1] + 1 = 2. Try coin 5: skip. dp[3] = 2.

Step 5: Fill dp[4]. Try coin 1: dp[3] + 1 = 3. Try coin 2: dp[2] + 1 = 2. Try coin 5: skip. dp[4] = 2.

Step 6: Fill dp[5]. Try coin 1: dp[4] + 1 = 3. Try coin 2: dp[3] + 1 = 3. Try coin 5: dp[0] + 1 = 1. dp[5] = 1.

Step 7: Fill dp[6]. Try coin 1: dp[5] + 1 = 2. Try coin 2: dp[4] + 1 = 3. Try coin 5: dp[1] + 1 = 2. dp[6] = 2.

Step 8: Fill dp[7]. Try coin 1: dp[6] + 1 = 3. Try coin 2: dp[5] + 1 = 2. Try coin 5: dp[2] + 1 = 2. dp[7] = 2.

Result: dp[7] = 2 (coins: 5 + 2 = 7).

Bottom-Up DP — Filling the Coin Change Table — Watch how we build the dp table from left to right, computing the minimum coins for each amount by checking all coin denominations and using previously computed results.

Algorithm

  1. Create an array dp of size amount + 1, initialized to amount + 1 (a value larger than any possible answer, acting as infinity).
  2. Set dp[0] = 0 (zero coins needed for zero amount).
  3. For each amount i from 1 to amount:
    • For each coin denomination c:
      • If i - c ≥ 0 and dp[i - c] + 1 < dp[i]:
        • Update dp[i] = dp[i - c] + 1
  4. If dp[amount] is still greater than amount, return -1 (impossible).
  5. Otherwise, return dp[amount].

Code

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        vector<int> dp(amount + 1, amount + 1);
        dp[0] = 0;
        
        for (int i = 1; i <= amount; i++) {
            for (int coin : coins) {
                if (coin <= i) {
                    dp[i] = min(dp[i], dp[i - coin] + 1);
                }
            }
        }
        
        return dp[amount] > amount ? -1 : dp[amount];
    }
};
class Solution:
    def coinChange(self, coins: list[int], amount: int) -> int:
        dp = [amount + 1] * (amount + 1)
        dp[0] = 0
        
        for i in range(1, amount + 1):
            for coin in coins:
                if coin <= i:
                    dp[i] = min(dp[i], dp[i - coin] + 1)
        
        return dp[amount] if dp[amount] <= amount else -1
class Solution {
    public int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, amount + 1);
        dp[0] = 0;
        
        for (int i = 1; i <= amount; i++) {
            for (int coin : coins) {
                if (coin <= i) {
                    dp[i] = Math.min(dp[i], dp[i - coin] + 1);
                }
            }
        }
        
        return dp[amount] > amount ? -1 : dp[amount];
    }
}

Complexity Analysis

Time Complexity: O(n × amount)

We have two nested loops: the outer loop runs amount times (from 1 to amount), and the inner loop runs n times (once per coin denomination). Each iteration does O(1) work (a comparison and a possible update). Total: O(n × amount). With n ≤ 12 and amount ≤ 10^4, this is at most 120,000 operations — very efficient.

Space Complexity: O(amount)

We use a single 1D array dp of size amount + 1. No recursion stack is needed since this is fully iterative. This is both the time-optimal and space-optimal solution for this problem.