Coin Change Solution

Problem

Given a list of coin denominations and a target amount, return the fewest number of coins needed to reach that amount exactly. You can use each denomination as many times as you want. Return -1 if no combination of coins can reach the target.

Example:

Input: coins = [1, 2, 5], amount = 11
Output: 3
Explanation: 5 + 5 + 1 = 11 using 3 coins

Counter-example (greedy fails): With coins = [1, 5, 11] and amount = 15, greedily picking the largest coin gives 11 + 1 + 1 + 1 + 1 = 5 coins. The actual minimum is 5 + 5 + 5 = 3 coins.

Intuition

The minimum coins needed for any amount depends only on smaller amounts — if you know the cheapest way to make amount - coin for every coin, you can compute the answer for amount in one pass. This optimal substructure lets us build a solution table bottom-up from 0 to the target, reusing each result exactly once.

Approach 1 — Brute Force Recursion

Try every coin at each step and recurse on the remaining amount. Without caching, overlapping subproblems are recomputed exponentially.

Steps:

Base case: if remaining == 0, return 0 (no coins needed).
Base case: if remaining < 0, return infinity (invalid path).
Try each coin, recursing on remaining - coin.
Return 1 plus the minimum valid recursive result, or -1 if none exist.

1def coin_change(coins: list[int], amount: int) -> int:
2    def min_coins(remaining: int) -> float:
3        if remaining == 0:
4            return 0
5        if remaining < 0:
6            return float('inf')
7        best = float('inf')
8        for coin in coins:
9            result = min_coins(remaining - coin)
10            best = min(best, result + 1)
11        return best
12
13    answer = min_coins(amount)
14    return answer if answer != float('inf') else -1

Time: O(S^n) — each call branches into n recursive calls, with no caching, over up to S levels
Space: O(S) — maximum call stack depth equals amount divided by the smallest coin

Approach 2 — Bottom-Up Dynamic Programming

Build a dp table where dp[i] holds the minimum coins for amount i. Use previously solved smaller amounts to compute each new entry in a single forward pass.

Steps:

Allocate dp of size amount + 1, initialized to amount + 1 as a sentinel (you can never need more coins than the amount itself).
Set dp[0] = 0 — zero coins are needed to make zero.
For each target from 1 to amount, and for each coin:
If coin <= target, update dp[target] = min(dp[target], dp[target - coin] + 1).
Return dp[amount] if it is still a valid value (≤ amount), otherwise -1.

1def coin_change(coins: list[int], amount: int) -> int:
2    dp = [amount + 1] * (amount + 1)  # sentinel: valid solutions need at most 'amount' coins
3    dp[0] = 0
4
5    for target in range(1, amount + 1):
6        for coin in coins:
7            if coin <= target:
8                dp[target] = min(dp[target], dp[target - coin] + 1)
9
10    return dp[amount] if dp[amount] <= amount else -1

Time: O(S × n) — for each of S amounts, we try all n coin denominations once
Space: O(S) — the dp array has one slot per amount from 0 to S

Complexity Summary

Approach	Time	Space	When to use
Brute Force Recursion	O(S^n)	O(S)	Never in production; useful only to understand why DP is needed
Bottom-Up DP	O(S × n)	O(S)	Always — no recursion overhead, handles large inputs without stack overflow

Common Mistakes

Initializing dp with 0 instead of a sentinel: Every entry except dp[0] must start at "infinity"; using 0 makes every target appear reachable with 0 coins, breaking all comparisons.
Overflowing when using Integer.MAX_VALUE as sentinel in Java/C++: Adding 1 to Integer.MAX_VALUE wraps to a negative number, making it look like a valid minimum. Use amount + 1 as the sentinel instead.
Off-by-one in dp array size: Allocating new int[amount] instead of new int[amount + 1] puts dp[amount] out of bounds — the table needs indices 0 through amount inclusive.
Trusting greedy intuition: Picking the largest coin first fails whenever a smaller combination is cheaper. The classic trap is coins like [1, 5, 11] with amount 15, where greedy picks 11 first but the optimum skips it entirely.
Returning the sentinel instead of -1: When dp[amount] still equals amount + 1 after filling the table, the amount is unreachable — return -1, not the sentinel value.

Coin Change — Solution