Back to Dynamic Programming
Q2Question 2 of 31

Coin Change II: number of ways to make an amount

Key Concepts
  • Coin Change II counts distinct combinations of denominations summing to an amount with unlimited reuse
  • Loop order is critical: coins outside and amounts inside counts combinations, not permutations
  • Base case dp[0] = 1 because there is exactly one way to make zero: use no coins
  • Transition dp[a] += dp[a-coin] accumulates the count of ways to form each amount
  • Swapping the loop order silently changes the answer from combinations to permutations
  • Time is O(amount * coins) and space is O(amount)
  • Use long or modular arithmetic to prevent overflow for large amounts

Definition

Coins in the outer loop, amounts in the inner loop, dp[a] += dp[a-coin], and dp[0] = 1 counts combinations not permutations.

Coin Change II is the unbounded-knapsack counting DP.

  • Count array dp[a] tracks the number of combinations that sum to amount a.
  • Base case dp[0] = 1 because there is exactly one way to make zero: take nothing.
  • Loop order coins OUTSIDE, amounts INSIDE ensures combinations not permutations.
  • Transition dp[a] += dp[a - coin] accumulates ways to form each amount.
  • Time is O(amount * coins) and space is O(amount).

A teller at National Bank of India wants to know how many different note combinations add up to a requested amount. For each denomination she adds in turn, she extends every smaller total by that note. Putting the coin loop outside stops her from counting 5-then-1 and 1-then-5 as two different ways.

Understanding the Concepts

What is the Coin Change II Problem?

Given coin denominations and a target amount, return the total number of distinct combinations that make up that amount. Order does not matter, so [1,2] and [2,1] are the same combination. Each coin may be reused unlimited times.

At National Bank of India, a cash-planning tool reports how many distinct note combinations could satisfy a withdrawal.

JAVA
package com.bank.service;

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

        for (int coin : coins) {               // coins OUTSIDE
            for (int a = coin; a <= amount; a++) {  // amounts INSIDE
                dp[a] += dp[a - coin];
            }
        }
        return dp[amount];
    }

    public static void main(String[] args) {
        int[] coins = {1, 2, 5};
        int amount = 5;
        System.out.println("Ways to make " + amount + ": " + change(amount, coins));
    }
}
TEXT
Ways to make 5: 4

Why Is the Loop Order Critical?

The loop order determines whether we count combinations or permutations. Coins outside means each denomination is fully processed before moving to the next, so the same multiset is never counted in a different order.

JAVA
package com.bank.core;

public class LoopOrderDemo {
    public static void main(String[] args) {
        int[] coins = {1, 2, 5};
        int amount = 5;

        // COMBINATIONS (coins outside)
        int[] dpComb = new int[amount + 1];
        dpComb[0] = 1;
        for (int coin : coins)
            for (int a = coin; a <= amount; a++)
                dpComb[a] += dpComb[a - coin];

        // PERMUTATIONS (amounts outside)
        int[] dpPerm = new int[amount + 1];
        dpPerm[0] = 1;
        for (int a = 1; a <= amount; a++)
            for (int coin : coins)
                if (a >= coin) dpPerm[a] += dpPerm[a - coin];

        System.out.println("Combinations: " + dpComb[amount]);  // 4
        System.out.println("Permutations: " + dpPerm[amount]);  // 9
    }
}
TEXT
Combinations: 4
Permutations: 9

How Does the DP Fill Step by Step?

Let us trace the fill for coins [1, 2, 5] and amount 5.

JAVA
package com.bank.core;

public class CoinChangeIITrace {
    public static void main(String[] args) {
        int[] coins = {1, 2, 5};
        int amount = 5;
        int[] dp = new int[amount + 1];
        dp[0] = 1;

        for (int coin : coins) {
            System.out.println("Processing coin: " + coin);
            for (int a = coin; a <= amount; a++) {
                dp[a] += dp[a - coin];
            }
            System.out.print("  dp = [");
            for (int i = 0; i <= amount; i++) System.out.print(dp[i] + (i < amount ? ", " : ""));
            System.out.println("]");
        }
    }
}
TEXT
Processing coin: 1
  dp = [1, 1, 1, 1, 1, 1]
Processing coin: 2
  dp = [1, 1, 2, 2, 3, 3]
Processing coin: 5
  dp = [1, 1, 2, 2, 3, 4]

How Is This Different from Coin Change I (Minimum)?

DIAGRAM
| Aspect | Coin Change II (Ways) | Coin Change I (Minimum) |
|---|---|---|
| Question | How many combinations? | Fewest coins needed? |
| DP value | Count | Minimum count |
| Base case | dp[0] = 1 | dp[0] = 0, rest = sentinel |
| Transition | dp[a] += dp[a-coin] | dp[a] = min(dp[a], dp[a-coin]+1) |
| Loop order | Coins outside (critical!) | Either order works |
| Unreachable | dp[amount] = 0 | dp[amount] = sentinel -> -1 |
JAVA
// Ways: dp[a] += dp[a - coin]  (accumulate)
// Min:  dp[a] = Math.min(dp[a], dp[a - coin] + 1)  (minimize)

What Are the Edge Cases?

Edge cases include: amount is zero (one way: empty combination), no coins given (zero ways for positive amounts), and single coin that does not divide the amount.

JAVA
package com.bank.core;

public class CoinIIEdgeCases {
    public static void main(String[] args) {
        System.out.println(CoinChangeII.change(0, new int[]{1, 2}));    // 1
        System.out.println(CoinChangeII.change(5, new int[]{}));        // 0
        System.out.println(CoinChangeII.change(3, new int[]{2}));       // 0 (3 not reachable by 2s)
        System.out.println(CoinChangeII.change(4, new int[]{2}));       // 1 (2+2)
    }
}
TEXT
1
0
0
1

What About Overflow for Large Amounts?

For large amounts with many coins, the count can grow very large. Use long or modular arithmetic to prevent overflow.

JAVA
package com.bank.core;

public class CoinIILong {
    public static long changeLong(int amount, int[] coins) {
        long[] dp = new long[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) {
        int[] coins = {1, 2, 5, 10, 20, 50, 100};
        System.out.println("Ways to make 500: " + changeLong(500, coins));
    }
}

What About the Recursive Approach?

The recursive approach with memoization uses a 2D memo table indexed by (coin index, remaining amount). This is top-down DP equivalent to the bottom-up approach.

JAVA
package com.bank.core;

import java.util.HashMap;
import java.util.Map;

public class CoinIIRecursive {
    private static Map<String, Integer> memo = new HashMap<>();

    public static int change(int[] coins, int index, int remaining) {
        if (remaining == 0) return 1;
        if (remaining < 0 || index >= coins.length) return 0;
        String key = index + "," + remaining;
        if (memo.containsKey(key)) return memo.get(key);

        int ways = change(coins, index, remaining - coins[index])  // use coin again
                 + change(coins, index + 1, remaining);             // skip to next coin
        memo.put(key, ways);
        return ways;
    }
}

What Are Common Interview Follow-Up Questions?

Interviewers commonly ask:

  • Count permutations instead: swap the loop order (amounts outside, coins inside).
  • Coin Change I: find the minimum coins instead of counting ways.
  • Limited coin supply: bounded knapsack with quantity constraints.
  • Print all combinations: use backtracking instead of DP.
JAVA
package com.bank.core;

public class CoinIIFollowUps {
    // Combinations -> Permutations: swap loop order
    // Count -> Minimize: change += to min
    // Count -> Enumerate: backtracking
    // Unlimited -> Limited: bounded knapsack
}

Visual Overview

DIAGRAM
  Loop Order Comparison:

  COMBINATIONS (correct for this problem):
  ┌──────────────────────────────────┐
  │ for each coin:                    │
  │   process ALL amounts with        │
  │   this coin before moving on      │
  │                                   │
  │ Coin 1: dp = [1,1,1,1,1,1]       │
  │ Coin 2: dp = [1,1,2,2,3,3]       │
  │ Coin 5: dp = [1,1,2,2,3,4]       │
  └──────────────────────────────────┘

  PERMUTATIONS (different problem):
  ┌──────────────────────────────────┐
  │ for each amount:                  │
  │   try ALL coins at this amount    │
  │                                   │
  │ [1,2] and [2,1] counted           │
  │ as separate ways                  │
  │ Result: 9 instead of 4            │
  └──────────────────────────────────┘

Key Takeaway

Coin Change II is a counting DP on the unbounded knapsack. I define dp[a] as the number of distinct combinations that sum to amount a, set dp[0] to 1, and leave the rest at zero. Then for each coin I sweep amounts from the coin value up to the target and add dp[a-coin].

The single most important detail is the loop order. The coin loop must be on the outside and the amount loop on the inside, because that counts each combination exactly once. If I reversed them I would count ordered sequences, so [1,2] and [2,1] would be treated as two different ways.

At National Bank of India, a cash-planning tool needed to report how many distinct note combinations could satisfy a withdrawal so the ATM team could gauge flexibility. I used this counting DP with the coin loop outside.

The classic interview mistake is swapping the loop order. It silently changes the answer from combinations to permutations without any compilation error or runtime exception. I always call this out explicitly because it is the most common bug candidates make on this problem.

Remember one sentence: coins outside, amounts inside, dp[0] = 1, and dp[a] += dp[a-coin] counts combinations not permutations.

---

Share
Use ← → arrow keys to navigate