AlgoMaster Logo

Coin Change

mediumFrequency8 min readUpdated June 23, 2026

Understanding the Problem

We need to find the minimum number of coins from a given set of denominations that sum up to a target amount. Each coin can be used unlimited times. If it is impossible to reach the target, we return -1.

A greedy strategy (always take the largest coin that fits) fails on some inputs. With coins [1, 3, 4] and amount 6, greedy picks 4 + 1 + 1 = 3 coins, but the optimal answer is 3 + 3 = 2 coins. The problem has overlapping subproblems and optimal substructure, the two hallmarks of dynamic programming.

If the minimum coin count were known for every amount below the target, the answer for the target would follow by trying each coin c and taking the best result for target - c. That recursive structure is the foundation of every approach below.

Key Constraints:

  • 1 <= coins.length <= 12 --> At most 12 denominations, so trying every coin at each step is cheap.
  • 0 <= amount <= 10^4 --> A DP table indexed by amount has at most 10,001 entries, small enough to hold in memory.
  • 1 <= coins[i] <= 2^31 - 1 --> Individual coins can exceed the amount. A coin larger than amount can never be part of a solution.

Approach 1: Recursion (Brute Force)

Intuition

To make amount A, pick any coin c from the set and solve the smaller subproblem of making amount A - c. Trying every coin and keeping the choice with the fewest total coins gives the answer for A.

Two base cases end the recursion: if A == 0, zero coins are needed. If A < 0, the current path overshot the target and is invalid, so it returns a large value to signal failure.

This explores every combination of coins, which is correct but exponential: the same subproblems are solved over and over across different branches of the recursion tree.

Algorithm

  1. Define a recursive function solve(remaining) that returns the minimum coins to make remaining, or a maximum sentinel value if it cannot be made.
  2. If remaining == 0, return 0.
  3. If remaining < 0, return the sentinel (this path is invalid).
  4. Initialize minCoins to the sentinel.
  5. For each coin, recursively solve for remaining - coin. If the result is valid and result + 1 is less than minCoins, update minCoins.
  6. Return minCoins. At the top level, call solve(amount) and translate the sentinel into -1.

Example Walkthrough

With coins = [1, 5, 10] and amount = 12, the recursion branches three ways at every level, once per coin.

0
1
1
5
2
10
coins
12
amount

solve(12) calls solve(11), solve(7), and solve(2), one per coin. Following the coin-10 branch: solve(2) can only proceed with coin 1, so it calls solve(1), which calls solve(0). solve(0) returns 0, so solve(1) = 1, solve(2) = 2, and this branch completes with 10 + 1 + 1 = 3 coins. The coin-5 branch does no better: its best path is 5 + 5 + 1 + 1 = 4 coins. The all-1s branch uses 12 coins. The minimum across branches is 3, which solve(12) returns.

The repeated work is visible even at this size. solve(2) is reached from the 10 branch, from the 5 + 5 branch, and from many paths that mix in 1-coins, and each time it is recomputed from scratch.

3
result

Code

The recursion re-solves the same subproblems many times. The next approach stores each result the first time it is computed.

Approach 2: Top-Down DP (Memoization)

Intuition

Memoization stores the result of solve(remaining) in a cache the first time it is computed. The remaining amount is the only parameter that changes between calls, and it ranges from 0 to amount, so a cache of size amount + 1 covers every subproblem. Once a value sits in the cache, every later call for that amount returns it directly.

Each subproblem is now solved exactly once, which turns the exponential recursion into polynomial work. The recursion logic itself does not change; the memo check and store wrap around it.

Algorithm

  1. Create a memo array of size amount + 1, initialized to a sentinel value (e.g., -2) meaning "not computed yet."
  2. Define solve(remaining) with the same logic as before.
  3. Before computing, check if memo[remaining] is already set. If so, return it.
  4. After computing the result, store it in memo[remaining] before returning.

Example Walkthrough

The trace below uses coins = [1, 3, 4] and amount = 6, the input where greedy fails. The recursion descends from solve(6) to the base case, then fills the memo on the way back up. solve(0) returns 0 directly without a memo write; the trace shows 0 at index 0 for readability.

1Initialize memo, all entries = -2 (not computed). Start solve(6).
0
-2
1
-2
2
-2
3
-2
4
-2
5
-2
6
-2
solve(6)
1/8

The top-level call returns memo[6] = 2, the two-coin solution 3 + 3.

Code

Memoization reaches the optimal time complexity, but it pays function-call overhead and risks stack overflow when the amount is large. Building the same table iteratively avoids both.

Approach 3: Bottom-Up DP (Optimal)

Intuition

Instead of starting from the target amount and recursing down, we can build the solution from the ground up. We create a table dp where dp[i] represents the minimum number of coins needed to make amount i. We start from dp[0] = 0 (zero coins for zero amount) and fill the table up to dp[amount].

For each amount i from 1 to amount, we try every coin. If a coin c is less than or equal to i, we can reach amount i by using one coin c plus the optimal solution for amount i - c. We take the minimum across all such coin choices.

This is the unbounded knapsack pattern. Each coin can be used any number of times, which is why dp[i - c] refers back into the same array instead of a previous row.

Algorithm

  1. Create array dp of size amount + 1, initialized to amount + 1 (a value larger than any valid answer, acting as "infinity").
  2. Set dp[0] = 0 (base case: zero coins for zero amount).
  3. For each amount i from 1 to amount:
    • For each coin c in coins:
      • If c <= i, set dp[i] = min(dp[i], dp[i - c] + 1).
  4. If dp[amount] is still amount + 1, return -1 (unreachable). Otherwise return dp[amount].

Example Walkthrough

The same input, coins = [1, 3, 4] and amount = 6, now fills the table from left to right. The sentinel value is amount + 1 = 7, and each entry dp[i] settles once every coin has been tried against it.

1Initialize: dp[0]=0 (base case), all others = 7 (infinity)
0
0
base
1
7
2
7
3
7
4
7
5
7
6
7
1/8

dp[6] = 2 is below the sentinel, so the function returns 2, matching the 3 + 3 solution found by memoization.

Code