Definition
Coin Change Number of Ways is the counting variant of the Unbounded Knapsack.
- Count array
dp[a]stores the number of distinct combinations that sum to amounta. - Base case is
dp[0] = 1because there is exactly one way to make zero: use no coins. - Coins outside, amounts inside loop order counts combinations (not permutations).
- Low-to-high sweep on amounts allows unlimited reuse of each denomination.
- Time is O(denominations * amount) and space is O(amount).
The National Bank of India wants to know how many distinct ways a cash dispenser can make a requested amount using available note denominations, where each note type is unlimited. Coin Change counts those distinct combinations without double-counting reordered sets.
Understanding the Concepts
What is the Coin Change Number of Ways Problem?
Given coin denominations and a total amount, count the number of distinct combinations that make up that amount. Each denomination can be used unlimited times. Order does not matter: using coins [1, 2] is the same combination as [2, 1].
At National Bank of India, the ATM operations team wants to know how many distinct note combinations can satisfy a withdrawal request.
package com.bank.service;
public class CoinChangeWays {
public static int countWays(int[] coins, int amount) {
int[] dp = new int[amount + 1];
dp[0] = 1; // one way to make zero: no coins
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[] denominations = {1, 2, 5};
int amount = 5;
System.out.println("Ways to make " + amount + ": " + countWays(denominations, amount));
}
}
Ways to make 5: 4
The four combinations are: [5], [2,2,1], [2,1,1,1], [1,1,1,1,1].
Why Does the Loop Order Matter?
The loop order is the single most important detail. Coins on the outside and amounts on the inside count combinations. Reversing the loops counts permutations (ordered sequences).
With coins outside, each denomination is fully considered before moving to the next, so the order in which coins are picked is fixed and no combination is counted in a different order.
package com.bank.core;
public class LoopOrderComparison {
// Combinations (coins outside): [1,2] and [2,1] are the same
public static int combinations(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];
}
// Permutations (amounts outside): [1,2] and [2,1] are different
public static int permutations(int[] coins, int amount) {
int[] dp = new int[amount + 1];
dp[0] = 1;
for (int a = 1; a <= amount; a++)
for (int coin : coins)
if (a >= coin) dp[a] += dp[a - coin];
return dp[amount];
}
public static void main(String[] args) {
int[] coins = {1, 2, 5};
System.out.println("Combinations for 5: " + combinations(coins, 5)); // 4
System.out.println("Permutations for 5: " + permutations(coins, 5)); // 9
}
}
Combinations for 5: 4
Permutations for 5: 9
How Does the DP Table Fill Step by Step?
Let us trace the DP for coins [1, 2, 5] and amount 5.
package com.bank.core;
public class CoinChangeTrace {
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("\nProcessing coin: " + coin);
for (int a = coin; a <= amount; a++) {
dp[a] += dp[a - coin];
System.out.println(" dp[" + a + "] += dp[" + (a - coin) + "] -> dp[" + a + "] = " + dp[a]);
}
}
System.out.println("\nTotal ways: " + dp[amount]);
}
}
Processing coin: 1
dp[1] += dp[0] -> dp[1] = 1
dp[2] += dp[1] -> dp[2] = 1
dp[3] += dp[2] -> dp[3] = 1
dp[4] += dp[3] -> dp[4] = 1
dp[5] += dp[4] -> dp[5] = 1
Processing coin: 2
dp[2] += dp[0] -> dp[2] = 2
dp[3] += dp[1] -> dp[3] = 2
dp[4] += dp[2] -> dp[4] = 3
dp[5] += dp[3] -> dp[5] = 3
Processing coin: 5
dp[5] += dp[0] -> dp[5] = 4
Total ways: 4
How Is This Different from Coin Change Minimum?
| Aspect | Coin Change Ways | Coin Change Minimum |
|---|---|---|
| Question | How many ways? | What is the fewest coins? |
| DP value | Count of combinations | Minimum number of coins |
| 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 for min |
package com.bank.core;
public class WaysVsMinimum {
// Ways: dp[a] += dp[a - coin] (accumulate counts)
// Min: dp[a] = Math.min(dp[a], dp[a - coin] + 1) (relax minimum)
}
What Are the Edge Cases?
Edge cases include: amount is zero (one way: no coins), no coins given (zero ways for any positive amount), and amount not reachable by any combination.
package com.bank.core;
public class CoinWaysEdgeCases {
public static void main(String[] args) {
// Amount 0: one way (empty combination)
System.out.println(CoinChangeWays.countWays(new int[]{1, 2}, 0)); // 1
// No coins: zero ways
System.out.println(CoinChangeWays.countWays(new int[]{}, 5)); // 0
// Amount not reachable
System.out.println(CoinChangeWays.countWays(new int[]{3}, 5)); // 0
}
}
1
0
0
What About Large Counts and Overflow?
For large amounts and many denominations, the count can grow very large and overflow an int. Use long or modular arithmetic to handle this.
package com.bank.core;
public class CoinWaysLong {
public static long countWaysLong(int[] coins, int amount) {
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 1000: " + countWaysLong(coins, 1000));
}
}
What About Unbounded vs 0/1 Knapsack?
The low-to-high sweep on amounts is what makes this unbounded: the same coin can contribute to dp[a] multiple times across increasing amounts. In 0/1 Knapsack (Subset Sum), the high-to-low sweep prevents reuse.
package com.bank.core;
public class UnboundedVsBounded {
// Unbounded (reuse allowed): sweep a from coin upward
// for (int a = coin; a <= amount; a++) dp[a] += dp[a - coin];
// 0/1 (no reuse): sweep a from amount downward
// for (int a = amount; a >= coin; a--) dp[a] += dp[a - coin];
}
What Are Common Interview Follow-Up Questions?
Interviewers commonly ask:
- Coin Change Minimum: find the fewest coins instead of counting ways.
- Count permutations instead of combinations: swap the loop order.
- Print all combinations: use backtracking instead of DP.
- Handle coins with limited supply: this becomes a bounded knapsack variant.
package com.bank.core;
public class CoinFollowUps {
// Combinations -> Permutations: swap loop order
// Count -> Enumerate: use backtracking
// Unlimited -> Limited: add quantity constraints
}
Visual Overview
Loop Order for Combinations vs Permutations:
COMBINATIONS (coins outside): PERMUTATIONS (amounts outside):
┌──────────────────────┐ ┌──────────────────────┐
│ for coin in coins: │ │ for a = 1 to amount: │
│ for a = coin to T: │ │ for coin in coins: │
│ dp[a] += ... │ │ dp[a] += ... │
└──────────────────────┘ └──────────────────────┘
Each coin processed fully At each amount, all coins
before next coin. are reconsidered.
[1,2] = [2,1] (same) [1,2] != [2,1] (different)
DP Fill for coins [1, 2, 5], amount 5:
After coin 1: [1, 1, 1, 1, 1, 1]
After coin 2: [1, 1, 2, 2, 3, 3]
After coin 5: [1, 1, 2, 2, 3, 4]
0 1 2 3 4 5
Key Takeaway
Coin Change Number of Ways is the counting variant of the Unbounded Knapsack pattern, and the subtle point an interviewer always looks for is the loop order. I keep an integer array where each slot counts the distinct combinations that form that amount, seeded with one way to make zero using no coins. Then I put the coin denominations in the outer loop and the amounts in the inner loop.
Processing one coin type completely before moving to the next is exactly what makes me count combinations rather than permutations. Because I never return to an earlier coin type once I advance, two sets that use the same coins in a different order are never counted twice. If I reversed the loops, placing amounts outside and coins inside, I would count ordered sequences, which answers a different question entirely.
At National Bank of India I used this for cash dispensers, where the operations team wanted to know how many distinct combinations of available note denominations could make a requested withdrawal. I ran the counting DP with coins outside and amounts inside.
The low-to-high sweep on amounts allows unlimited reuse of each denomination. This contrasts with the 0/1 Knapsack high-to-low sweep that prevents reuse. For large counts, using long or modular arithmetic prevents overflow.
Remember one sentence: coins outside and amounts inside counts combinations, not permutations, with dp[0] = 1 and dp[a] += dp[a - coin].
---