A kiosk has to make change of 6 with coins 1, 3, and 4. The intern’s hopper is greedy: largest coin that still fits. Out comes 4, then 1, then 1 — three coins. Two 3s would have been enough. Finance asks a second question the same afternoon: how many different packs sum to 5? The intern counts 1+2 and 2+1 as two packs. They are one combination. Then a test amount 7 with only 2s and 4s returns 0, and a dashboard treats that as “zero coins, done.”

Coin change is unbounded: the same denomination may be used again. Fewest coins and combination count share a 1D table and a nested loop. They do not share an answer type, and they are not 0/1 knapsack.

This post is those two loops. Families, greedy-vs-DP vocabulary, and the catalog live on the Algorithms Roadmap. When each item exists once, that is 0/1 Knapsack — a different job. Do not reuse its pick-or-skip table here.

Two jobs that share a name

“Coin change” is two specs. Mixing them is the production bug.

Fewest coins. Return the smallest number of coins whose values sum to amount. Order does not matter. If no multiset works, there is no answer — typically -1, not a silent 0. Amount 0 is 0 coins: the empty pack.

Count combinations. Return how many unordered packs sum to amount. {1, 2} and {2, 1} are one combination. Amount 0 is 1 way: use nothing.

Both allow the same denomination to repeat. Neither is “list the ordered sequences.” If the ticket wanted permutations, name that ticket; do not “fix” the combination loop by swapping the nests and still calling it coin change.

Note: Impossible is not 0 unless 0 is the answer. Zero coins is correct for amount 0. It is a lie for “cannot make 7 from even coins.” Use a sentinel in the table; map the sentinel to -1 (or throw) at the boundary.

Unbounded is not 0/1 knapsack

0/1 Knapsack is pick or skip when each item exists once. A snack with one sandwich in the hopper cannot be taken twice. This post’s coins are a denomination list: as long as the remaining amount allows it, another 3 is legal.

That shows up in the 1D loop direction. For unbounded min-coins and combination count, walk the amount up after you pick a coin. The cell you read, dp[x - coin], may already include this same coin — that is the repeat. Walking the amount down is the 0/1 compaction: you refuse to reuse the item in the same pass. Do not copy that direction from the knapsack post and call it change-making.

Forward on x is the unbounded contract. You do not need a 2D pick-or-skip grid for either job here.

Greedy “always the largest coin” is a third procedure. It is correct on some canonical systems (US coins are the usual interview example). It is wrong on [1, 3, 4] making 6. This post is the DP that stays correct when the hopper is an arbitrary positive list. If you already know the system is canonical and you only need fewest coins, greedy is a different bill — still not a reason to skip the impossible check.

Fewest coins: recurrence and a sentinel

Let dp[x] be the fewest coins that sum to x. Then:

dp[0] = 0
dp[x] = min over coins c ≤ x of  dp[x - c] + 1
        (or impossible, if no such c works)

You do not enumerate packs. At each amount x you try “one more coin c” on top of an already-optimal x - c. Because a coin may repeat, that x - c may itself have used c.

Initialize dp[1..amount] to a sentinel larger than any feasible answer. The worst feasible pack is amount coins of 1, so sentinel = amount + 1 is enough. After the loops, if dp[amount] is still the sentinel, return -1.

Note: Do not use Integer.MAX_VALUE as the sentinel and then write dp[x - coin] + 1. That add wraps to a negative, and Math.min will happily keep the wrap. amount + 1 cannot wrap on this add: the left side is at most amount, the right side at most amount + 1.

A walk: coins 1, 3, 4 making 6

Classic trap. Greedy takes 4+1+1 (three). The table finds two.

coins = [1, 3, 4], amount = 6, inf = 7

x:        0  1  2  3  4  5  6
init:     0  7  7  7  7  7  7

coin 1:   0  1  2  3  4  5  6
coin 3:   0  1  2  1  2  3  2
coin 4:   0  1  2  1  1  2  2

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

After coin 1 every amount is feasible and terrible. Coin 3 at x = 3 reads dp[0] + 1 and becomes 1. At x = 6 it reads dp[3] + 1: that dp[3] already used a 3, so this is the second 3. Coin 4 improves dp[4] to 1 but dp[2] + 1 is 3, which loses to the existing 2. The repeat is the point of walking x forward.

Impossible stays the sentinel. Coins [2, 4], amount 7: every odd cell remains inf. dp[7] >= inf → -1. Returning 0 would look like “already made.”

Java: min coins in one array

There is no Arrays.minCoins. Positive denominations, non-negative amount, one int[] of size amount + 1.

static int minCoins(int[] coins, int amount) {
    int inf = amount + 1;
    int[] dp = new int[amount + 1];
    java.util.Arrays.fill(dp, inf);
    dp[0] = 0;
    for (int coin : coins) {
        if (coin <= 0) {
            throw new IllegalArgumentException("need positive 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];
}

Amount 0 returns 0 without special-casing: dp[0] stays 0. A coin larger than amount skips the inner loop. Empty coins leaves every positive cell at inf and returns -1 unless amount == 0.

Note: The method answers “how many coins,” not “which coins.” If the hopper log needs the pack, keep a prev[x] (the coin that last improved dp[x]) in the same pass and walk back from amount. Do not run a second search for a pack that sums to dp[amount] and call it the same algorithm — ties disagree.

Combinations, not permutations

Let ways[x] be the number of unordered packs that sum to x. ways[0] = 1. Add one denomination at a time. For each coin, walk x from coin up to amount and do ways[x] += ways[x - coin]. Packs that use this coin are counted after packs that do not. Because the coin loop is the outer loop, {1, 2} is recorded once, when 2 is processed on top of packs already made from 1.

Swap the nests — amount outer, coin inner — and you count orderings. [1, 2] and [2, 1] both appear. That is a different spec. Name it permutations if you need it. Do not ship it as “number of ways to make change.”

A short walk. Coins [1, 2, 5], amount 5. Four combinations: five 1s; three 1s and a 2; one 1 and two 2s; one 5.

ways[0] = 1, rest 0. coins = [1, 2, 5], amount = 5

after 1:  1  1  1  1  1  1
after 2:  1  1  2  2  3  3
after 5:  1  1  2  2  3  4

ways[5] = 4

After coin 2, ways[3] became 2: {1,1,1} and {1,2}. Coin 5 adds ways[0] onto ways[5]. If you had walked amounts in the outer loop, 1+2 and 2+1 would both increment and you would report more than four.

Java: count the packs

Same 1D array. Different initializer, different answer type, same forward inner loop. Use long — combination counts grow fast, and an int wrap looks like a small legal total.

static long combinationCount(int[] coins, int amount) {
    long[] ways = new long[amount + 1];
    ways[0] = 1;
    for (int coin : coins) {
        if (coin <= 0) {
            throw new IllegalArgumentException("need positive coins");
        }
        for (int x = coin; x <= amount; x++) {
            ways[x] += ways[x - coin];
        }
    }
    return ways[amount];
}

Amount 0 returns 1. Impossible amounts stay 0 here because “zero combinations” is the real answer — that is the one job where a leftover 0 is honest. Do not copy that return into minCoins.

Note: Outer for (int coin : coins) then inner x is the combination contract. Reverse it and you have permutation count, even if every identifier still says combination.

Complexity

WhatCostWhy
Time (either job)O(n · amount)Each of n coins visits each cell x
Extra spaceO(amount)One 1D table; input coins are whoever owns them
Naive pack searchExponentialRecursion without a table retries the same remainder
2D tableO(n · amount) extraSame asymptotics; 1D is enough when you walk x forward
OutputO(1) or O(k)The count, or a reconstructed pack of k coins

amount is the numeric target, not n. A target of a million with twenty denominations is twenty million inner steps, not “linear in the coin list.” 1D, forward x, sentinel on min-coins. A correct recursive search with no memo is still the wrong default on a vending remainder.

When not to use this DP

Skip these loops when the job is not “unbounded coins, fewest or unordered packs.”

  • Each item exists once. That is 0/1 Knapsack. Walking x downward to block reuse is that post’s 1D trick, not a flag you pass to minCoins.
  • You needed the pack, not only the count. The int / long return does not remember coins. Keep prev[x] in the min-coins pass. Do not reconstruct from the count afterward and hope the tie matches the hopper.
  • Greedy is legal and you know it. Canonical systems (classic US denominations) can take largest-first for fewest coins. Arbitrary lists cannot. Do not greedy [1, 3, 4] and cite the cash-drawer heuristic.
  • Order matters. Sequences, not packs, are permutations. Swap the nests on purpose and name the spec. Do not call the larger number “combinations.”
  • Bounded copies. “At most three 5s” is neither unbounded nor 0/1. It is a different DP (often an extra copy loop or a 0/1 expansion of duplicated items). Not this post.
  • The target is money with a decimal. Scale to integer cents first, then run this. Floating amount is not a cell index.
  • Zero or negative denominations. A 0 coin in the inner loop never moves x and will hang. Throw at the boundary, as above.

Unbounded, positive coins, one global amount — that is the job. Pick-or-skip once, ordered sequences, and “at most k of this coin” are other procedures.

Cheat sheet

Jobs:        (1) fewest coins  (2) combination count (order does not matter)
Unbounded:   same denomination may repeat; walk x forward
Min coins:   dp[0]=0; dp[x]=min(dp[x], dp[x-coin]+1); sentinel=amount+1
Impossible:  dp[amount] still sentinel → -1  (not 0)
Combinations: ways[0]=1; coin outer, x inner; ways[x]+=ways[x-coin]
Permutations: amount outer, coin inner — different spec, larger number
Not 0/1:     each item once is knapsack; downward x blocks reuse
Greedy:      wrong on [1,3,4] making 6 (3+3 beats 4+1+1)
Time/space:  O(n·amount) / O(amount)
JDK:         none — write the loops

Do:

  • Name the spec first: fewest coins vs combination count.
  • Initialize min-coins with a sentinel; map it to -1 at the return.
  • Walk x from coin up so a denomination may repeat.
  • Keep combination loops as coin-outer; use long for the counts.

Don’t:

  • Return 0 for an amount you cannot make on the min-coins job.
  • Walk x downward and still claim unbounded reuse.
  • Count [1,2] and [2,1] as two packs.
  • Re-teach 0/1 pick-or-skip here — that is the knapsack post.
  • Look for Arrays.coinChange. There is not one.

Wrap-up

Coin change replaces “try packs” with one cell per remainder. Unbounded means the same coin may feed the next cell; walking x forward is that contract. Fewest coins and combination count share the nest and split on initializer, update, and what a leftover 0 means. Impossible min-coins needs a sentinel. Combination 0 is a real count.

The layout is a list of denominations plus an integer amount. The procedure is this pass. When each item exists once, start from 0/1 Knapsack. When the letters of two strings may match without sitting next to each other, that is the next DP job — pick it from the Algorithms Roadmap rather than stretching this table.

Next optional step in the series Longest shared subsequence when the letters need not sit next to each other. LCS: Longest Shared Subsequence Without Requiring Contiguous