LeetCode · #518

Coin Change II Solution

Return the number of combinations that make up the given amount using coins of given denominations (unlimited supply).

Section One · Problem

Problem Statement

🏷️

Difficulty

Medium

🔗

LeetCode

Problem #518

🏗️

Pattern

DP — unbounded knapsack (count)

Given coins of different denominations and a total amount, return the number of combinations (not permutations) that sum to amount. Each coin can be used unlimited times.

Example

Input: amount = 5, coins = [1,2,5]
Output: 4 // 5=5, 5=2+2+1, 5=2+1+1+1, 5=1+1+1+1+1

Constraints

• 1 ≤ coins.length ≤ 300 • 1 ≤ coins[i] ≤ 5000, all unique • 0 ≤ amount ≤ 5000

Section Two · Approach 1

Recursion — Exponential

For each coin, decide how many to use (0, 1, 2, …). Recurse on remaining amount. Count all ways the remaining amount reaches 0.

Why it works

Exhaustive — tries every combination of coin counts.

Why we can do better

Problem: Overlapping subproblems. DP builds bottom-up: iterate coins in the outer loop (to avoid counting permutations) and amounts in the inner loop.

Java — Recursive

 class Solution {
public int change(int amount, int[] coins) {
return dfs(coins, amount, 0);
    }
private int dfs(int[] coins, int rem, int idx) {
if (rem == 0) return 1;
if (rem < 0) return 0;
int ways = 0;
for (int i = idx; i < coins.length; i++) // start from idx to avoid permutations
ways += dfs(coins, rem - coins[i], i);
return ways;
    }
}

Python — Recursive

 class Solution:
def change(self, amount: int, coins: list[int]) -> int:
def dfs(rem, idx):
if rem == 0: return 1 if rem < 0: return 0 return sum(dfs(rem - coins[i], i) for i in range(idx, len(coins)))
return dfs(amount, 0)

Metric	Value
Time	Exponential
Space	O(amount)

Section Three · Approach 2

Unbounded Knapsack DP — O(n · amount)

dp[a] = number of combinations to make amount a. Iterate coins in outer loop (ensures combinations, not permutations), amounts in inner loop forward (unbounded — can reuse coins).

💡 Mental model: Imagine a cashier filling a tip jar. She first tries all amounts using only pennies, then adds nickels to the mix, then dimes. By adding one denomination at a time, she counts combinations (1p+1p+1n is the same as 1n+1p+1p — only counted once). If she mixed denominations in the inner loop, she'd count both orderings separately — giving permutations instead.

Algorithm

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

🎯 When to recognize this pattern: "Count combinations (order doesn't matter) to reach target with unlimited supply." Coins outer, amounts inner = combinations. Amounts outer, coins inner = permutations (LC 377 Combination Sum IV). The loop order is the key distinction.

Combinations vs Permutations — the loop order: Outer coin loop means each coin type is "introduced" once. dp[a] accumulates ways using coins[0..i] only. Inner coin loop would recount 1+2 and 2+1 as different permutations.

Section Four · Trace

Visual Walkthrough

Trace for amount=5, coins=[1,2,5].

Coin Change II — Unbounded Knapsack

Section Five · Implementation

Code — Java & Python

Java — Unbounded knapsack

 class Solution {
public int change(int amount, int[] coins) {
int[] dp = new int[amount + 1];
        dp[0] = 1;
for (int coin : coins) // outer: coin type for (int a = coin; a <= amount; a++) // inner: forward (unbounded)
dp[a] += dp[a - coin];
return dp[amount];
    }
}

Python — Unbounded knapsack

 class Solution:
def change(self, amount: int, coins: list[int]) -> int:
        dp = [0] * (amount + 1)
        dp[0] = 1 for coin in coins:
for a in range(coin, amount + 1):
                dp[a] += dp[a - coin]
return dp[amount]

Section Six · Analysis

Complexity Analysis

Approach	Time	Space	Trade-off
Recursion	Exponential	O(amount)	TLE for large inputs
2D DP table	O(n·amount)	O(n·amount)	Correct but extra space
1D unbounded knapsack ← optimal	O(n·amount)	O(amount)	Clean 1D array; coin-outer guarantees combinations

LC 322 vs LC 518: LC 322 finds the minimum number of coins (uses min). LC 518 counts the number of combinations (uses +=). Same DP structure, different aggregation.

Section Seven · Edge Cases

Edge Cases & Pitfalls

Case	Input	Why It Matters
amount = 0	`coins=[1,2], amount=0`	One way: use no coins. dp[0]=1.
No coins	`coins=[], amount=5`	Outer loop doesn't execute. dp[5]=0.
Single coin	`coins=[3], amount=6`	Only way: 3+3. dp[6]=1.
Impossible	`coins=[2], amount=3`	Can't make 3 with only 2s. dp[3]=0.
Large amount	`amount=5000`	dp array of 5001 ints. O(5000 × 300) = 1.5M ops. Fine.

⚠ Common Mistake: Swapping the loop order — putting amounts in the outer loop and coins in the inner loop. This counts permutations (1+2 and 2+1 are different). For combinations, coins must be the outer loop so each denomination is "introduced" once.

← Back to DP — 2D problems

LearningTree

LC 518 · Coin Change II — Solution & Explanation | DSA Guide