Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

Coin Change

HARDProblemSolveExternal Links

Description

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

Return the fewest number of coins needed to make up that exact amount. If no combination of coins can produce the exact amount, return -1.

You may assume that you have an infinite supply of each coin denomination.

Examples

Example 1

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

Output: 3

Explanation: The optimal combination uses two coins of denomination 5 and one coin of denomination 1: 5 + 5 + 1 = 11. No combination of fewer than 3 coins can sum to 11 with these denominations. For instance, using two 5-coins only reaches 10, and using one 5-coin plus denominations 1 and 2 requires at least 5 + 2 + 2 + 2 = 11 which is 4 coins.

Example 2

Input: coins = [2], amount = 3

Output: -1

Explanation: The only coin available has denomination 2. Any number of 2-coins always produces an even sum (2, 4, 6, ...), so it is impossible to make exactly 3. We return -1.

Example 3

Input: coins = [1], amount = 0

Output: 0

Explanation: The target amount is 0, which means no coins are needed at all. Zero coins always sum to zero, so we return 0.

Constraints

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

Editorial

Brute Force

Intuition

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

Imagine you are at a vending machine that only accepts exact change. You have unlimited coins of each type. To figure out the minimum coins needed, you could try subtracting each coin denomination from the target amount and recursively solve the smaller problem. For amount 11 with coins [1, 2, 5], you would ask: what if I use a 1-coin first (leaving 10)? What if I use a 2-coin first (leaving 9)? What if I use a 5-coin first (leaving 6)? For each choice, you recursively find the minimum coins for the remaining amount, then pick the choice that results in the fewest total coins.

This is a classic recursive exploration: at every step, branch into all coin choices, recurse on the remaining amount, and take the minimum result.

Step-by-Step Explanation

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

Step 1: Call coinChange(11). We try subtracting each coin denomination from 11.

Step 2: Three recursive branches are created:

  • Subtract coin 1 → coinChange(10)
  • Subtract coin 2 → coinChange(9)
  • Subtract coin 5 → coinChange(6)

Step 3: Explore coinChange(10). It also creates three branches:

  • Subtract coin 1 → coinChange(9)
  • Subtract coin 2 → coinChange(8)
  • Subtract coin 5 → coinChange(5)

Step 4: Notice that coinChange(9) appears twice in our recursion tree — once as a direct child of coinChange(11) and once as a child of coinChange(10). This is an overlapping subproblem! Both branches will independently compute the exact same answer.

Step 5: Explore coinChange(9) from the first occurrence. It branches into coinChange(8), coinChange(7), and coinChange(4). Notice coinChange(8) is also duplicated — it appears under both coinChange(10) and coinChange(9).

Step 6: Expand coinChange(6) into coinChange(5), coinChange(4), and coinChange(1). More duplicates emerge: coinChange(5) appears under both coinChange(10) and coinChange(6), and coinChange(4) appears under both coinChange(9) and coinChange(6).

Step 7: The tree continues growing exponentially. Each level multiplies the number of nodes by up to 3 (one per coin). Many subproblems like coinChange(5), coinChange(4), etc. are recomputed dozens or hundreds of times.

Step 8: Eventually, base cases are reached: coinChange(0) returns 0 (no coins needed for amount 0), and any call with a negative amount returns -1 (impossible).

Step 9: Results propagate back up: coinChange(1) = 1, coinChange(2) = 1, coinChange(5) = 1, coinChange(6) = 2, coinChange(10) = 2, and finally coinChange(11) = min(1+coinChange(10), 1+coinChange(9), 1+coinChange(6)) = min(3, 4, 3) = 3.

Step 10: The answer is 3 coins (5 + 5 + 1), but the brute force explored an enormous number of redundant paths to find it.

Brute Force Recursion — Exponential Tree with Overlapping Subproblems — Watch how the recursion tree expands exponentially, with identical subproblems like change(9) and change(8) appearing multiple times across different branches.

Algorithm

  1. Define a recursive function coinChange(amount) that returns the minimum coins needed for the given amount
  2. Base cases:
    • If amount == 0, return 0 (no coins needed)
    • If amount < 0, return -1 (impossible to make negative amount)
  3. For each coin denomination in the coins array:
    • Recursively call coinChange(amount - coin)
    • If the result is valid (not -1), track result + 1 as a candidate
  4. Return the minimum candidate found, or -1 if no valid combination exists

Code

#include <vector>
#include <climits>
using namespace std;

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

Complexity Analysis

Time Complexity: O(S^n) where S is the amount and n is the number of coin denominations

At each recursive call, we branch into n choices (one per coin). The maximum recursion depth is S (subtracting coin value 1 each time). This creates a tree with up to n^S nodes in the worst case. For S = 10,000 and n = 12, this is astronomically large.

Space Complexity: O(S)

The recursion stack can go as deep as S levels (when repeatedly subtracting the smallest coin, which could be 1). Each stack frame uses O(1) space, so total stack space is O(S).

Why This Approach Is Not Efficient

The brute force recursion has exponential time complexity O(S^n) because it recomputes the same subproblems over and over. For example, coinChange(9) is computed from multiple parent calls independently, and each of those computations spawns its own subtree of redundant work.

With the given constraints (amount up to 10^4 and up to 12 coin types), the recursion tree can have billions of nodes. Even for our small example with amount = 11, the partial tree we traced already had duplicate computations at just 3 levels deep.

The root cause is overlapping subproblems: the recursive structure naturally leads to the same sub-amounts being solved many times. If we could remember (cache) the result of each sub-amount the first time we compute it, we would never redo that work. This insight leads directly to memoization.

Recursion tree for coinChange(11) showing overlapping subproblems highlighted with red connections
Recursion tree for coinChange(11) showing overlapping subproblems highlighted with red connections

Better Approach - Top-Down Dynamic Programming (Memoization)

Intuition

The brute force wastes time because it solves the same subproblems repeatedly. The fix is simple: the first time we compute coinChange(x) for any amount x, we store the result in a dictionary (memo table). Before computing any subproblem, we first check if it is already in the memo — if so, we return the cached result immediately instead of recursing.

Think of it like a student solving practice problems. The first time they solve 'minimum coins for amount 9', they work through it fully and write the answer in their notebook. The next time a problem requires 'minimum coins for amount 9' as a sub-step, they just look it up in their notebook instead of solving it from scratch.

This transforms the exponential recursion into a linear scan over unique subproblems. There are only amount + 1 unique subproblems (amounts 0 through 11), and each is solved at most once.

Step-by-Step Explanation

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

Step 1: Initialize memo = {}. Call coinChange(11).

Step 2: coinChange(11) explores its branches. DFS goes deep, eventually reaching small subproblems and base cases first.

Step 3: Base case reached: coinChange(0) = 0. Store memo[0] = 0. Resolving upward: coinChange(1) = min(coinChange(0)+1) = 1. Store memo[1] = 1.

Step 4: Continue resolving small amounts: coinChange(2) = min(memo[1]+1, memo[0]+1) = min(2, 1) = 1 (use coin 2). Store memo[2] = 1.

Step 5: More amounts resolved and cached: memo[3] = 2, memo[4] = 2, memo[5] = 1 (one coin of 5!). Each computed exactly once.

Step 6: Compute coinChange(6) = min(memo[5]+1, memo[4]+1, memo[1]+1) = min(2, 3, 2) = 2. Store memo[6] = 2. All lookups are O(1) from the memo.

Step 7: Continue: memo[7] = 2, memo[8] = 3, memo[9] = 3. When computing coinChange(9), the sub-calls to coinChange(8), coinChange(7), and coinChange(4) all find their answers in memo instantly.

Step 8: Compute coinChange(10). It needs coinChange(9), coinChange(8), and coinChange(5) — ALL already cached! coinChange(10) = min(memo[9]+1, memo[8]+1, memo[5]+1) = min(4, 4, 2) = 2. Store memo[10] = 2.

Step 9: Back at coinChange(11). It needs coinChange(10), coinChange(9), and coinChange(6) — all in memo.

Step 10: coinChange(11) = min(memo[10]+1, memo[9]+1, memo[6]+1) = min(3, 4, 3) = 3.

Step 11: Return 3. Each of the 12 subproblems (amounts 0 through 11) was computed exactly once. No redundant work.

Memoized Recursion — Each Subproblem Solved Only Once — Watch how the memo dictionary grows as subproblems are resolved, and how duplicate subproblems are instantly looked up instead of recomputed.

Algorithm

  1. Create an empty dictionary memo to cache results
  2. Define a recursive function dp(remaining):
    • If remaining < 0, return -1 (impossible)
    • If remaining == 0, return 0 (base case)
    • If remaining is in memo, return memo[remaining] (cached result)
    • For each coin denomination:
      • Recursively call dp(remaining - coin)
      • Track the minimum valid result + 1
    • Store the result in memo[remaining] and return it
  3. Call dp(amount) and return the result

Code

#include <vector>
#include <unordered_map>
#include <climits>
using namespace std;

class Solution {
public:
    unordered_map<int, int> memo;
    
    int coinChange(vector<int>& coins, int amount) {
        if (amount < 0) return -1;
        if (amount == 0) return 0;
        if (memo.count(amount)) return memo[amount];
        
        int minCoins = INT_MAX;
        for (int coin : coins) {
            int result = coinChange(coins, amount - coin);
            if (result >= 0) {
                minCoins = min(minCoins, result + 1);
            }
        }
        
        memo[amount] = (minCoins == INT_MAX) ? -1 : minCoins;
        return memo[amount];
    }
};
class Solution:
    def coinChange(self, coins: list[int], amount: int) -> int:
        memo = {}
        
        def dp(remaining):
            if remaining < 0:
                return -1
            if remaining == 0:
                return 0
            if remaining in memo:
                return memo[remaining]
            
            min_coins = float('inf')
            for coin in coins:
                result = dp(remaining - coin)
                if result >= 0:
                    min_coins = min(min_coins, result + 1)
            
            memo[remaining] = min_coins if min_coins != float('inf') else -1
            return memo[remaining]
        
        return dp(amount)
import java.util.HashMap;
import java.util.Map;

class Solution {
    private Map<Integer, Integer> memo = new HashMap<>();
    
    public int coinChange(int[] coins, int amount) {
        if (amount < 0) return -1;
        if (amount == 0) return 0;
        if (memo.containsKey(amount)) return memo.get(amount);
        
        int minCoins = Integer.MAX_VALUE;
        for (int coin : coins) {
            int result = coinChange(coins, amount - coin);
            if (result >= 0 && result < minCoins) {
                minCoins = result + 1;
            }
        }
        
        int answer = (minCoins == Integer.MAX_VALUE) ? -1 : minCoins;
        memo.put(amount, answer);
        return answer;
    }
}

Complexity Analysis

Time Complexity: O(n × S) where n is the number of coin denominations and S is the amount

There are S + 1 unique subproblems (amounts 0 through S). Each subproblem is computed at most once and cached. For each subproblem, we iterate over all n coins to find the minimum. Total work: (S + 1) × n = O(n × S).

Space Complexity: O(S)

The memo dictionary stores at most S + 1 entries (one per unique amount). The recursion stack can be at most S levels deep (when repeatedly subtracting 1). So total space is O(S) for the memo plus O(S) for the stack = O(S).

Why This Approach Is Not Efficient

While memoization reduces the time from exponential to O(n × S), it still relies on recursion. For this problem, the recursion depth can be as large as the amount itself (up to 10,000). This creates two issues:

  1. Stack overflow risk: Each recursive call consumes stack memory. With amount = 10,000 and coin 1 available, the recursion can go 10,000 levels deep. Many programming environments have default stack limits around 1,000–10,000 frames, making this borderline or outright crashing.

  2. Function call overhead: Each recursive call has overhead — pushing parameters onto the stack, saving return addresses, and restoring state on return. For 10,000+ recursive calls, this adds measurable constant-factor overhead compared to a simple loop.

  3. Unpredictable memory access: Recursion visits subproblems in a depth-first order that depends on which coins are tried first. This leads to less cache-friendly memory access patterns compared to a sequential iteration.

A bottom-up iterative approach eliminates all three issues: it uses a simple loop (no recursion stack), fills a table sequentially (cache-friendly), and has minimal per-step overhead.

Optimal Approach - Bottom-Up Dynamic Programming

Intuition

Instead of starting from the target amount and recursing downward, we can build the solution from the bottom up. We create a table where dp[i] represents the minimum number of coins needed to make amount i. We start with the smallest amount (0) and work our way up to the target.

Think of climbing a staircase where each step represents an amount. At the ground floor (amount 0), you need 0 coins. For each higher step, you look back at the steps you could reach this step from (by using one coin of each denomination), and pick the one that required the fewest coins, then add 1.

For example, to compute dp[11], you check: can I reach 11 by adding a 1-coin to amount 10 (dp[10] + 1)? By adding a 2-coin to amount 9 (dp[9] + 1)? By adding a 5-coin to amount 6 (dp[6] + 1)? The minimum of these is your answer.

This iterative approach fills the table from left to right in a single pass, avoiding recursion entirely.

Step-by-Step Explanation

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

Step 1: Create dp array of size 12 (indices 0 to 11). Set dp[0] = 0, all others = ∞ (meaning "not yet achievable").

Step 2: Fill dp[1]. Try coin 1: dp[1-1]+1 = dp[0]+1 = 1. Coins 2 and 5 are too large. dp[1] = 1.

Step 3: Fill dp[2]. Coin 1: dp[1]+1 = 2. Coin 2: dp[0]+1 = 1. Coin 5: too large. dp[2] = min(2, 1) = 1.

Step 4: Fill dp[3]. Coin 1: dp[2]+1 = 2. Coin 2: dp[1]+1 = 2. Coin 5: too large. dp[3] = 2.

Step 5: Fill dp[4]. Coin 1: dp[3]+1 = 3. Coin 2: dp[2]+1 = 2. Coin 5: too large. dp[4] = 2.

Step 6: Fill dp[5]. Coin 1: dp[4]+1 = 3. Coin 2: dp[3]+1 = 3. Coin 5: dp[0]+1 = 1. dp[5] = 1! A single 5-coin covers the entire amount.

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

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

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

Step 10: Fill dp[9]. Coin 1: dp[8]+1 = 4. Coin 2: dp[7]+1 = 3. Coin 5: dp[4]+1 = 3. dp[9] = 3.

Step 11: Fill dp[10]. Coin 1: dp[9]+1 = 4. Coin 2: dp[8]+1 = 4. Coin 5: dp[5]+1 = 2. dp[10] = 2. Two 5-coins!

Step 12: Fill dp[11]. Coin 1: dp[10]+1 = 3. Coin 2: dp[9]+1 = 4. Coin 5: dp[6]+1 = 3. dp[11] = min(3, 4, 3) = 3.

Step 13: Return dp[11] = 3. The answer is 3 coins: 5 + 5 + 1 = 11.

Bottom-Up DP Table — Building Solutions from Amount 0 to 11 — Watch how the DP table fills left to right, with each cell computed from previously solved smaller amounts using each available coin denomination.

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 (base case: zero coins needed for amount 0)
  3. For each amount i from 1 to amount:
    • For each coin denomination coin in coins:
      • If coin <= i (the coin fits), update dp[i] = min(dp[i], dp[i - coin] + 1)
  4. If dp[amount] is still greater than amount, return -1 (no valid combination exists)
  5. Otherwise, return dp[amount]

Code

#include <vector>
#include <algorithm>
using namespace std;

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 = [float('inf')] * (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] != float('inf') else -1
import java.util.Arrays;

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 × S) where n is the number of coin denominations and S is the amount

The outer loop runs S times (from 1 to amount). For each iteration, the inner loop checks all n coins. Each check is O(1). Total: S × n = O(n × S). With S up to 10,000 and n up to 12, this is at most 120,000 operations — very fast.

Space Complexity: O(S)

We use a single 1D array of size S + 1 to store the DP table. No recursion stack is needed since the approach is purely iterative. This is optimal space for this problem since we need to store the answer for each sub-amount.