Coin Change Problem — Why Greedy Fails for [1,3,4] Sets

Every payment system, vending machine firmware, and change-dispensing ATM in the world is quietly solving a version of this problem. When a cashier's drawer runs low on quarters, the register software recalculates optimal change combinations on the fly. When a cryptocurrency exchange breaks a large order into smaller fills, it's optimizing a coin-change variant under the hood. This isn't an academic puzzle — it's load-bearing infrastructure.

The naive approach — try every possible combination recursively — collapses catastrophically at scale. With just 10 coin types and a target of 1000, the recursion tree explodes into millions of redundant sub-problems. The same sub-problems get solved over and over, burning CPU time you'll never get back. Dynamic Programming eliminates that waste entirely by guaranteeing each sub-problem is solved exactly once and its result reused. That's the contract DP makes with you.

By the end of this article you'll be able to implement both the minimum-coins variant and the count-of-ways variant from scratch in Java, explain the recurrence relation cold, optimize from O(amount · coins) space down to O(amount), handle every edge case that trips people up in production and in interviews, and articulate the difference between the two DP approaches well enough to teach it to someone else. Let's build this up piece by piece.

What is Coin Change? — Plain English

The Coin Change problem: given a set of coin denominations and a target amount, find the minimum number of coins needed to make that amount. Coins can be reused any number of times (unbounded). Greedy doesn't always work — with coins [1, 3, 4] and amount 6, greedy picks 4+1+1=3 coins but the optimal is 3+3=2 coins.

This is the classic unbounded knapsack / complete knapsack problem. Dynamic programming builds the answer bottom-up: first solve for amount 0 (trivial: 0 coins), then for amount 1, 2, ... up to the target, reusing already-computed results.

How Coin Change Works — Step by Step

Define dp[amount] = minimum number of coins to make 'amount'.

1. Initialize dp[0] = 0 (zero coins needed for amount 0).
2. Initialize dp[1..target] = infinity (not yet reachable).
3. For each amount from 1 to target:
4. For each coin denomination c:
5. If c <= amount and dp[amount - c] is not infinity:
6. dp[amount] = min(dp[amount], dp[amount - c] + 1)
7. Return dp[target]. If still infinity, return -1 (impossible).

Time complexity: O(amount * len(coins)). Space: O(amount).

Worked Example — Tracing the Algorithm

Coins = [1, 3, 4]. Target = 6.

Initialize: dp = [0, INF, INF, INF, INF, INF, INF]

amount=1: try coin 1: dp[0]+1=1. dp[1]=1. dp = [0, 1, INF, INF, INF, INF, INF]

amount=2: try coin 1: dp[1]+1=2. dp[2]=2. dp = [0, 1, 2, INF, INF, INF, INF]

amount=3: try coin 1: dp[2]+1=3. try coin 3: dp[0]+1=1. min(3,1)=1. dp[3]=1. dp = [0, 1, 2, 1, INF, INF, INF]

amount=4: try coin 1: dp[3]+1=2. try coin 3: dp[1]+1=2. try coin 4: dp[0]+1=1. min=1. dp[4]=1. dp = [0, 1, 2, 1, 1, INF, INF]

amount=5: try coin 1: dp[4]+1=2. try coin 3: dp[2]+1=3. try coin 4: dp[1]+1=2. min=2. dp[5]=2. dp = [0, 1, 2, 1, 1, 2, INF]

amount=6: try coin 1: dp[5]+1=3. try coin 3: dp[3]+1=2. try coin 4: dp[2]+1=3. min=2. dp[6]=2. dp = [0, 1, 2, 1, 1, 2, 2]

Answer: dp[6] = 2 coins. The combination is coin 3 + coin 3.

Java Implementation — Minimum Number of Coins

Here's a clean Java implementation of the bottom-up DP for Coin Change. It uses a 1D array to minimise space, handles the sentinel overflow issue, and returns -1 when impossible.

package io.thecodeforge;

public class CoinChange {
    public static int minCoins(int[] coins, int amount) {
        // max value to use as sentinel (safe from overflow when +1)
        int max = amount + 1;
        int[] dp = new int[amount + 1];
        java.util.Arrays.fill(dp, max);
        dp[0] = 0;

        for (int a = 1; a <= amount; a++) {
            for (int coin : coins) {
                if (coin <= a) {
                    dp[a] = Math.min(dp[a], dp[a - coin] + 1);
                }
            }
        }

        return dp[amount] == max ? -1 : dp[amount];
    }

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

Edge Cases and Common Traps

Edge cases that break naive implementations:

1. Amount = 0: result is 0 coins. Ensure dp[0]=0 and loop starts at 1.
2. Impossible amount: e.g., coins={2}, amount=3. Return -1 correctly.
3. Large coin value: if coin > amount, skip it inside the loop to avoid index out of bounds. Use if (coin <= a) guard.
4. Unsorted coins: algorithm handles any order, but sorted coins may give minor cache benefits.
5. Very large amounts (≥10^6): O(amount*coins) becomes heavy. Consider greedy for canonical sets or heuristic pruning.

Coin Change II: Count Number of Combinations

The second variant: count the number of distinct ways to make the amount using unlimited coins. Order does not matter — (1,2) and (2,1) count as one combination.

Recurrence: dp[a] += dp[a - coin] (for each coin), but careful: outer loop must be over coins, inner loop over amounts to avoid counting permutations as separate combinations.

Initialize dp[0] = 1 (one way: use no coins). For each coin, for each amount from coin to target: dp[a] += dp[a - coin].

Example: coins={1,2}, amount=4 → combinations: {1+1+1+1}, {1+1+2}, {2+2} → 3 ways.

package io.thecodeforge;

public class CoinChangeCombinations {
    public static int countWays(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        dp[0] = 1;
        for (int coin : coins) {
            for (int a = coin; a <= amount; a++) {
                dp[a] += dp[a - coin];
            }
        }
        return dp[amount];
    }

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

Naive Recursion: Why You'll Fail a Phone Screen If This Is All You Write

You hit a problem, you grab recursion. Fine for understanding. Lethal for production.

The naive recursive approach treats every coin choice as a branch. At each step you either include the current coin and keep exploring (because infinite supply means you can reuse it), or you skip it and move to the previous coin. That's 2 decisions per call, and the recursion depth goes up to sum. You're looking at O(2^sum) time. For sum = 100, that's more operations than atoms in the observable universe.

Space isn't better. The call stack grows linearly with sum, so O(sum) memory just for the recursion frames. A stack overflow is not a feature request — it's a crash in production.

This approach is useful for exactly one thing: proving you understand the recurrence relation. Write it in an interview, then immediately say "But this is exponential, so let's memoize." If you ship this, you're wasting cloud spend and user patience.

```java // io.thecodeforge — dsa tutorial

public class CoinChangeRecursive { public int countWays(int[] coins, int sum) { return countWaysHelper(coins, coins.length, sum); }

private int countWaysHelper(int[] coins, int n, int sum) { if (sum == 0) return 1; if (sum < 0 || n == 0) return 0; // include current coin, exclude current coin return countWaysHelper(coins, n, sum - coins[n-1]) + countWaysHelper(coins, n-1, sum); }

public static void main(String[] args) { CoinChangeRecursive solver = new CoinChangeRecursive(); int[] coins = {1, 2, 3}; int sum = 4; System.out.println(solver.countWays(coins, sum)); } } ```

Output: `` 4 ``

// io.thecodeforge — dsa tutorial

public class CoinChangeRecursive {
    public int countWays(int[] coins, int sum) {
        return countWaysHelper(coins, coins.length, sum);
    }

    private int countWaysHelper(int[] coins, int n, int sum) {
        if (sum == 0) return 1;
        if (sum < 0 || n == 0) return 0;
        // include current coin, exclude current coin
        return countWaysHelper(coins, n, sum - coins[n-1]) 
             + countWaysHelper(coins, n-1, sum);
    }

    public static void main(String[] args) {
        CoinChangeRecursive solver = new CoinChangeRecursive();
        int[] coins = {1, 2, 3};
        int sum = 4;
        System.out.println(solver.countWays(coins, sum));
    }
}

Top-Down DP (Memoization): Stop Solving the Same Problem Twice

You figured out the recursive brute-force. Now realize that count(coins, n, sum) gets called with the exact same arguments thousands of times. Why compute the same subtree more than once? Store results in a 2D table dp[n][sum] where dp[i][j] holds the number of ways to make sum j using first i coins.

Time drops from O(2^sum) to O(n sum) because each state (i, j) is computed exactly once. Space is O(n sum) for the memo table plus O(sum) for recursion stack — still better than exponential, but not optimal.

The pattern is universal: before recursing, check if dp[i][j] is already computed. After computing, store it. This is memoization. Costs a dictionary lookup but saves an entire recursion branch.

```java // io.thecodeforge — dsa tutorial

import java.util.Arrays;

public class CoinChangeMemo { private int[][] memo;

public int countWays(int[] coins, int sum) { memo = new int[coins.length + 1][sum + 1]; for (int[] row : memo) Arrays.fill(row, -1); return countWaysHelper(coins, coins.length, sum); }

private int countWaysHelper(int[] coins, int n, int sum) { if (sum == 0) return 1; if (sum < 0 || n == 0) return 0; if (memo[n][sum] != -1) return memo[n][sum];

memo[n][sum] = countWaysHelper(coins, n, sum - coins[n-1]) + countWaysHelper(coins, n-1, sum); return memo[n][sum]; }

public static void main(String[] args) { CoinChangeMemo solver = new CoinChangeMemo(); int[] coins = {2, 5, 3, 6}; int sum = 10; System.out.println(solver.countWays(coins, sum)); } } ```

Output: `` 5 ``

// io.thecodeforge — dsa tutorial

import java.util.Arrays;

public class CoinChangeMemo {
    private int[][] memo;

    public int countWays(int[] coins, int sum) {
        memo = new int[coins.length + 1][sum + 1];
        for (int[] row : memo) Arrays.fill(row, -1);
        return countWaysHelper(coins, coins.length, sum);
    }

    private int countWaysHelper(int[] coins, int n, int sum) {
        if (sum == 0) return 1;
        if (sum < 0 || n == 0) return 0;
        if (memo[n][sum] != -1) return memo[n][sum];

        memo[n][sum] = countWaysHelper(coins, n, sum - coins[n-1]) 
                     + countWaysHelper(coins, n-1, sum);
        return memo[n][sum];
    }

    public static void main(String[] args) {
        CoinChangeMemo solver = new CoinChangeMemo();
        int[] coins = {2, 5, 3, 6};
        int sum = 10;
        System.out.println(solver.countWays(coins, sum));
    }
}

Space-Optimized DP: When Your Cloud Bill Reaches Five Figures

Your top-down DP works. But it uses O(n * sum) memory. For sum = 10000 and n = 100, that's a million integers. That's megabytes for nothing.

Look at the recurrence again: dp[n][sum] only depends on dp[n-1][sum] and dp[n][sum - coin]. That means your current row i only needs the previous row i-1 and the same row i. You don't need to keep the entire 2D table.

Implement it with a single 1D array of size sum + 1. Update it in two passes for each coin: first iterate j from coin to sum (inclusive), and for each, add dp[j - coin]. That's it. Space drops to O(sum).

```java // io.thecodeforge — dsa tutorial

public class CoinChangeSpaceOpt { public int countWays(int[] coins, int sum) { int[] ways = new int[sum + 1]; ways[0] = 1;

for (int coin : coins) { for (int j = coin; j <= sum; j++) { ways[j] += ways[j - coin]; } } return ways[sum]; }

public static void main(String[] args) { CoinChangeSpaceOpt solver = new CoinChangeSpaceOpt(); int[] coins = {1, 2, 3}; int sum = 4; System.out.println(solver.countWays(coins, sum)); } } ```

Output: `` 4 ``

This is the version you should ship. It's fast, memory-efficient, and the loop order matters: outer loop over coins, inner loop from coin to sum. Flip them and you'll count permutations instead of combinations — a different problem.

// io.thecodeforge — dsa tutorial

public class CoinChangeSpaceOpt {
    public int countWays(int[] coins, int sum) {
        int[] ways = new int[sum + 1];
        ways[0] = 1;

        for (int coin : coins) {
            for (int j = coin; j <= sum; j++) {
                ways[j] += ways[j - coin];
            }
        }
        return ways[sum];
    }

    public static void main(String[] args) {
        CoinChangeSpaceOpt solver = new CoinChangeSpaceOpt();
        int[] coins = {1, 2, 3};
        int sum = 4;
        System.out.println(solver.countWays(coins, sum));
    }
}