Coin Change Problems

Coin change is a classic unbounded knapsack pattern: each coin can be used unlimited times. This lesson covers minimum coins (LeetCode 322), number of combinations (518), greedy vs DP, and full solutions in C, Java, and Python with output trace tables.

Overview

Given coin denominations and a target amount, common questions are:

• Minimum coins — fewest coins to make exact amount (or −1 if impossible)
• Count combinations — how many distinct multisets of coins sum to amount
• Count permutations — order matters (different loop order in DP)

Unbounded coin DP pattern:
  dp[0] = base case (0 coins or 1 way)
  for each amount a from 1 .. target:
      for each coin c:
          use dp[a - c] to update dp[a]

Greedy vs Dynamic Programming

Greedy (always pick largest coin) works for canonical systems like US coins {1, 5, 10, 25} but fails for arbitrary denominations.

Coin Change I — Minimum Coins

Problem: Given coins and amount, return the fewest coins needed, or −1 if impossible.

Recurrence: dp[a] = min(dp[a], dp[a − c] + 1) for each coin c ≤ a

Base: dp[0] = 0; initialize other cells to ∞ (or amount + 1)

Minimum Coins Code (C, Java, Python)

Python

def coin_change(coins, amount):
    """LeetCode 322 — minimum coins for exact amount. O(amount × len(coins))."""
    INF = amount + 1
    dp = [INF] * (amount + 1)
    dp[0] = 0  # zero coins needed for amount 0

    for a in range(1, amount + 1):
        for c in coins:
            if c <= a:
                # try using coin c: one coin + best for remainder
                dp[a] = min(dp[a], dp[a - c] + 1)

    return dp[amount] if dp[amount] != INF else -1


if __name__ == "__main__":
    tests = [([1, 2, 5], 11), ([2], 3), ([1, 3, 4], 6)]
    for coins, amount in tests:
        print(f"coins={coins}, amount={amount} → {coin_change(coins, amount)}")

Java

public class CoinChangeMin {

    /** Minimum coins — bottom-up unbounded knapsack style. */
    public static 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 a = 1; a <= amount; a++) {
            for (int c : coins) {
                if (c <= a) {
                    dp[a] = Math.min(dp[a], dp[a - c] + 1);
                }
            }
        }
        return dp[amount] == INF ? -1 : dp[amount];
    }

    public static void main(String[] args) {
        System.out.println(coinChange(new int[]{1, 2, 5}, 11));  // 3
        System.out.println(coinChange(new int[]{2}, 3));           // -1
        System.out.println(coinChange(new int[]{1, 3, 4}, 6));     // 2
    }
}

C

#include <stdio.h>

#define MAX_AMT 1000

/* Minimum coins for amount; returns -1 if impossible */
int coin_change_min(int coins[], int n, int amount) {
    int dp[MAX_AMT + 1];
    int INF = amount + 1;
    int a, i, c;

    for (a = 0; a <= amount; a++) dp[a] = INF;
    dp[0] = 0;

    for (a = 1; a <= amount; a++) {
        for (i = 0; i < n; i++) {
            c = coins[i];
            if (c <= a && dp[a - c] + 1 < dp[a]) {
                dp[a] = dp[a - c] + 1;
            }
        }
    }
    return dp[amount] == INF ? -1 : dp[amount];
}

int main(void) {
    int c1[] = {1, 2, 5}, c2[] = {2}, c3[] = {1, 3, 4};
    printf("%d\n", coin_change_min(c1, 3, 11)); /* 3 */
    printf("%d\n", coin_change_min(c2, 1, 3));  /* -1 */
    printf("%d\n", coin_change_min(c3, 3, 6));  /* 2 */
    return 0;
}

Minimum Coins Output & Trace

Program output (all three languages)

DP trace — coins = [1, 2, 5], amount = 11

Coin Change II — Combinations

Problem: Count how many combinations of coins sum to amount (order does not matter).

Key: Loop over coins outer, amount inner to avoid counting permutations twice.

Recurrence: dp[a] += dp[a − c] for each coin c

Combinations Code (C, Java, Python)

Python

def coin_change_combinations(coins, amount):
    """LeetCode 518 — count combinations (order ignored)."""
    dp = [0] * (amount + 1)
    dp[0] = 1  # one way to make amount 0: use no coins

    for c in coins:                    # outer: each coin type once
        for a in range(c, amount + 1):
            dp[a] += dp[a - c]         # add ways that use coin c

    return dp[amount]


if __name__ == "__main__":
    print(coin_change_combinations([1, 2, 5], 5))   # 4
    print(coin_change_combinations([1, 2, 5], 11))  # 11

Java

public class CoinChangeCombinations {

    public static int change(int amount, int[] coins) {
        int[] dp = new int[amount + 1];
        dp[0] = 1;

        for (int c : coins) {
            for (int a = c; a <= amount; a++) {
                dp[a] += dp[a - c];
            }
        }
        return dp[amount];
    }

    public static void main(String[] args) {
        int[] coins = {1, 2, 5};
        System.out.println(change(5, coins));   // 4
        System.out.println(change(11, coins));  // 11
    }
}

C

#include <stdio.h>

#define MAX_AMT 1000

int coin_change_ways(int coins[], int n, int amount) {
    int dp[MAX_AMT + 1] = {0};
    int i, a, c;

    dp[0] = 1;

    for (i = 0; i < n; i++) {
        c = coins[i];
        for (a = c; a <= amount; a++) {
            dp[a] += dp[a - c];
        }
    }
    return dp[amount];
}

int main(void) {
    int coins[] = {1, 2, 5};
    printf("%d\n", coin_change_ways(coins, 3, 5));   /* 4 */
    printf("%d\n", coin_change_ways(coins, 3, 11));  /* 11 */
    return 0;
}

Combinations Output & Trace

Program output

DP trace — coins = [1, 2, 5], amount = 5 (combinations)

Unbounded Knapsack Connection

Coin change is the unbounded subset-sum variant: unlimited copies of each item (coin).

More Examples

Example 1: Impossible amount

Example 2: Greedy failure (again)

Example 3: Complexity summary

Approach Comparison

A = amount, C = number of coin types, n = number of coins sorted for greedy.

Real-Life Applications

Coin change models any situation where you must reach an exact total using a fixed set of denominations—minimizing pieces or counting distinct ways.

Interview Tips

1. Clarify: minimum coins, count combinations, or count permutations?
2. State dp[a] meaning before writing loops.
3. Mention pseudo-polynomial time O(amount × coins).
4. For combinations vs permutations, explain outer/inner loop order.
5. Give greedy counterexample [1,3,4], amount=6.
6. Return −1 when min coins impossible; 0 combinations when amount unreachable.
7. Connect to knapsack problems (unbounded variant).