Difficulty: Medium1-D Dynamic Programming

Coin Change

Problem in Plain English

Given coin denominations with unlimited supply, find the smallest number of coins that sums to amount, or -1 when the amount cannot be formed.

Problem Statement

Given positive denominations in coins and a target amount, choose as many copies of each denomination as needed. Return the minimum number of coins whose total is exactly the target. Return -1 if no choice reaches it. Return zero for amount zero.

Coin order does not change a combination, and the input array remains unchanged.

Constraints

Coin count is between 1 and 12.
Every denomination is an integer from 1 through $2^{31}-1$ .
The target amount is an integer from 0 through $10^4$ .

Examples

Example 1

Input: coins = [1, 2], amount = 3
Output: 2

The sequences [1, 2] and [2, 1] use two coins, whereas [1, 1, 1] uses three. No denomination equals 3, so one coin cannot suffice.

Example 2

Input: coins = [2], amount = 3
Output: -1

Every total made from copies of 2 is even, so the odd target 3 is unreachable.

Example 3

Input: coins = [1], amount = 0
Output: 0

The empty selection already totals zero. Adding any positive coin would exceed the target.

Example 4

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

The selection [5, 5, 1] reaches 11 with three coins. Two coins total at most 10, so three is minimal.

Example 5

Input: coins = [1, 3, 4], amount = 6
Output: 2

Two copies of 3 reach 6. Taking the largest coin 4 first would require two further 1s, showing why greedy choice fails.

Intuition

Remove one coin from a solution and what remains is a smaller version of the same problem. With denominations [1, 2] and target 3, choosing 1 leaves remainder 2, while choosing 2 leaves remainder 1. Both continuations need one more coin, so the answer is two. Searching every coin order repeats these remainders; a table can instead solve each amount once. Largest-first greedy choices are unsafe: [1, 3, 4] and target 6 need two 3s, while taking 4 first needs three coins.

Approaches

Recursive Coin Search

Solution Details

Reveal Recursive Coin Search: intuition, complexity, and code

Intuition

Try each affordable first coin and recursively search its remainder, keeping the cheapest successful continuation. No remainder is remembered, so different coin orders repeat the same work. The snippets simulate recursive calls with explicit frames: each frame records its remainder, next coin index and best answer so far. This preserves exhaustive depth-first search while avoiding runtime call-stack limits at target 10000.

Step-by-Step Logic

Use sentinel amount + 1, which exceeds any possible answer because every coin is worth at least 1. For a zero target return 0; otherwise create a frame [remainder, nextCoin, best]. Example 1 begins [3, 0, 4].
Inspect the next denomination and advance the frame index before descending. Skip coins above the remainder. An exact match improves best to 1; otherwise push a fresh child frame. In Example 1, coin 1 takes remainder 3 to 2, then 2 to 1.
When a frame has tried every coin, pop it and pass one plus its best reachable answer to its parent. Remainder 1 finishes at 1; remainder 2 first receives 2, then coin 2 improves its best to 1.
Continue every branch, even a repeated remainder. The root receives 2 via coin 1, then independently searches remainder 1 via coin 2 and receives 2 again. Return root minimum 2, translating only the unreachable sentinel to -1.

Why It Works

For remainder zero, zero coins is correct. For any positive remainder, every valid selection starts with an affordable coin and leaves a strictly smaller remainder. Assuming those smaller searches are correct, adding one coin to each reachable result includes every possible first choice, and taking the minimum gives the optimum. If none succeeds, the remainder is unreachable. Positive coins ensure termination. Each explicit frame resumes after its child finishes and receives that child result exactly once, implementing the same recurrence as recursive calls without memoization.

Dry Run

Recursive Coin Search: variable states at each step
Event	Active frames (remainder, nextCoin, best), bottom to top	Result passed
Start	[3,0,4]	none
Root tries coin 1	[3,1,4]; [2,0,4]	none
Remainder 2 tries coin 1	[3,1,4]; [2,1,4]; [1,0,4]	none
Remainder 1 tries coin 1 exactly	[3,1,4]; [2,1,4]; [1,1,1]	best becomes 1
Remainder 1 skips coin 2; pop	[3,1,4]; [2,1,2]	1 + 1 = 2 to remainder 2
Remainder 2 tries coin 2 exactly	[3,1,4]; [2,2,1]	best improves to 1
Pop remainder 2	[3,1,2]	1 + 1 = 2 to root
Root tries coin 2	[3,2,2]; [1,0,4]	repeated remainder, no cache
Remainder 1 tries coin 1 exactly	[3,2,2]; [1,1,1]	best becomes 1
Remainder 1 skips coin 2; pop	[3,2,2]	candidate 2 leaves root best 2
Root exhausted; pop	empty	return 2

Complexity Analysis

Time Complexity

O(n^A + A)

Space Complexity

O(A+1)

Let n be the denomination count and A the target. Each descent reduces the remainder by at least one, giving at most A live frames. For n at least 2, scanning n coins in each positive-remainder frame gives the conservative exponential upper bound O(n^A); with one coin there are O(A) frames and checks. A zero target takes constant time. Each frame stores three integers, for O(A+1) peak auxiliary space including the stack container. Total frame allocations may be exponential; only the active path remains live. The input is not copied or mutated. Highly branching maximum targets are impractical for this teaching baseline.

Code

Solution.java

1import java.util.ArrayDeque;2
3class Solution {4    public int coinChange(int[] coins, int amount) {5        if (amount == 0) return 0;6        int unreachable = amount + 1;7        // Frames simulate calls: remainder, next coin index, best result.8        ArrayDeque<int[]> stack = new ArrayDeque<>();9        stack.push(new int[] {amount, 0, unreachable});10        while (!stack.isEmpty()) {11            int[] frame = stack.peek();12            if (frame[1] == coins.length) {13                int answer = stack.pop()[2];14                if (stack.isEmpty()) return answer == unreachable ? -1 : answer;15                if (answer != unreachable) {16                    stack.peek()[2] = Math.min(stack.peek()[2], answer + 1);17                }18                continue;19            }20            int coin = coins[frame[1]++];21            // Compare before subtracting; even the largest int denomination is safe.22            if (coin > frame[0]) continue;23            int remainder = frame[0] - coin;24            if (remainder == 0) frame[2] = 1;25            else stack.push(new int[] {remainder, 0, unreachable});26        }27        return -1;28    }29}

Hints

Hint 1

Consider every possible first coin rather than choosing the largest.

Hint 2

The answer for a remainder depends only on that remainder, not on the coin order used to reach it.

Hint 3

Seed amount zero with zero coins and fill smaller amounts before larger ones, carrying a separate unreachable value.

Edge Cases

A zero target needs zero coins for any denominations, even when all coins exceed the target.
A target smaller than every coin is impossible: [5, 2147483647] and target 3 return -1.
The odd target 3 with only coin 2 is unreachable, despite having a smaller affordable coin.
Having coin 1 guarantees reachability but does not guarantee greedy optimality: [1,3,4] and target 6 return 2.
An exact denomination needs one coin; repeated uses remain legal, such as [2] and target 4 returning 2.

Common Mistakes and Interview Tips

Largest-first greedy fails for [1,3,4] and target 6; explain why arbitrary denomination systems require exploring alternatives.
Adding one to an unguarded maximum-integer sentinel can overflow. Use A+1 and add only to reachable results.
Returning the sentinel directly exposes an impossible count instead of the required -1.
Filling amounts in descending order reads unfinished dependencies and can accidentally impose single-use semantics.
Interview tip: distinguish minimizing coin count from counting combinations, and explain the smaller-remainder invariant before coding.
The explicit stack prevents stack overflow but does not remove exponential repeated work; only the table approach shares results.

Key Takeaway

An unlimited-choice minimum can be expressed as one choice plus an optimal smaller capacity. Once positive choices make dependencies strictly smaller, increasing-capacity dynamic programming replaces a repeated search with one calculation per state.