A canteen till has to make exact change of amount from a hopper of denominations. Ops wants the fewest coins, not a printed pack. The intern grabbed largest-first. Amount 8 from [1, 4, 6] came back as 6+1+1 (three). Two 4s would have been enough. A second intern recursed every coin against the remainder; a forty-cent stub returned. A four-hundred-cent line was still forking when lunch started.

Coin Change asks for the fewest coins that sum to amount, or -1. An array of denominations is the hopper. Recursing every remainder uses that and still pays an exponential tree. Greedy largest-first is a third procedure and is wrong on this hopper.

This is an interview writeup, not the combinations lecture. The coin change tutorial owns unbounded packs, the forward 1D loop, and why that is not 0/1 knapsack. Here we only fill a min-count array.

The problem

Given an int[] coins of positive denominations and a non-negative int amount, return the fewest coins whose values sum to amount. A denomination may be used any number of times. Order does not matter. If no multiset works, return -1. Amount 0 is 0 coins.

coins = [1, 4, 6], amount = 8   →   2     4 + 4   (greedy 6+1+1 is 3)
coins = [2, 4],    amount = 7   →  -1     odds stay unreachable
coins = [5],       amount = 0   →   0

Note: Impossible is -1, not 0. Zero coins is correct only for amount 0. Counting unordered packs is a different ticket — that is the tutorial’s combination loop, not this return type.

Recursing every remainder is the honest brute force

From remaining left, try each coin c, recurse on left - c, and take 1 + the best feasible child. Hitting 0 costs 0 coins. Going negative is dead. Correct. Exponential: the same remainder is expanded under every ordering of coins.

int coinRec(int[] coins, int amount) {
    return from(coins, amount);
}

int from(int[] coins, int left) {
    if (left == 0) {
        return 0;
    }
    if (left < 0) {
        return -1;
    }
    int best = Integer.MAX_VALUE;
    for (int c : coins) {
        int sub = from(coins, left - c);
        if (sub >= 0) {
            best = Math.min(best, sub + 1);
        }
    }
    return best == Integer.MAX_VALUE ? -1 : best;
}

At a tiny amount this is a rounding error. At a lunch-rush total you paid a remainder tree for a question a 1D table answers: fewest for x is 1 plus fewest for some x - c? Memoizing from(left) is the same recurrence on demand. Greedy is not this brute: it is a different, sometimes wrong, shortcut.

One array: min coins to each amount

Let dp[x] be the fewest coins that sum to x. Seed dp[0] = 0. Fill the rest with a sentinel larger than any feasible pack — amount + 1 is enough (at worst amount ones). For each coin, walk x from coin up to amount and set dp[x] = min(dp[x], dp[x - coin] + 1). Walking x up is the unbounded contract the tutorial already named: dp[x - coin] may already have used this coin.

If dp[amount] is still the sentinel, return -1.

You need the whole 0..amount row. Two rolling integers are the climbing-stairs story; they are not this story. You cannot collapse the table: every smaller amount is a possible x - c.

coins = [1, 4, 6], amount = 8, inf = 9

x:        0  1  2  3  4  5  6  7  8
init:     0  9  9  9  9  9  9  9  9
coin 1:   0  1  2  3  4  5  6  7  8
coin 4:   0  1  2  3  1  2  3  4  2
coin 6:   0  1  2  3  1  2  1  2  2

dp[8] = 2   (4 + 4)
greedy  = 3   (6 + 1 + 1)

Coin 6 improves dp[6] to 1 but dp[8] stays 2: dp[2] + 1 is 3. The Java is that fill:

int coinChange(int[] coins, int amount) {
    int inf = amount + 1;
    int[] dp = new int[amount + 1];
    for (int i = 1; i <= amount; i++) {
        dp[i] = inf;
    }
    dp[0] = 0;
    for (int coin : coins) {
        for (int x = coin; x <= amount; x++) {
            dp[x] = Math.min(dp[x], dp[x - coin] + 1);
        }
    }
    return dp[amount] >= inf ? -1 : dp[amount];
}

Time is O(n · amount) — each coin against each reachable x. Space is O(amount) for the table. Rolling two integers would drop the remainders you still read.

Note: Do not sentinel with Integer.MAX_VALUE. The add wraps; Math.min keeps the wrap. amount + 1 cannot wrap on this add. Returning 0 for unreachable 7 from [2, 4] looks like “already made.”

What interviewers usually poke next

  • Greedy on US coins. Canonical hoppers can be greedy. This prompt is an arbitrary list. Name the [1, 4, 6] counterexample and keep the table.
  • Count combinations, not min coins. Different return type. Point at the coin change post and stop. Swapping the loop nests there counts permutations.
  • Which coins, not how many. Keep a prev[x] (the coin that last improved dp[x]) and walk back from amount. The int answer does not remember a pack.
  • 0/1 hopper (each coin once). Then you walk x down. That is knapsack compaction, not this problem.
  • Memo DFS on remainder. Same recurrence, O(n · amount) after the fill, extra stack. Name it, then go back to the array.

You are done with this problem when you can walk [1, 4, 6] making 8 to 2 on a whiteboard, return -1 for unreachable odds, and say out loud why largest-first is not a proof and why the combinations tutorial is a different question.