518. Coin Change II (Medium)

Problem

Given an amount and an array of coin denominations, return the number of distinct ways to make amount using unlimited coins of each denomination.

Example

• amount = 5, coins = [1, 2, 5] → 4 (5; 2+2+1; 2+1+1+1; 1+1+1+1+1)
• amount = 3, coins = [2] → 0

LeetCode 518 · Link · Medium

Try it yourself

Python

▶ Run Python ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

TypeScript

▶ Run TS ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Approach 1: Recursive with coin index

At each step, for coin c, choose “include another c” or “move to next coin.”

Python

def change(amount, coins):
    def f(i, remaining):
        if remaining == 0:                              # L1: O(1) base: made the amount
            return 1
        if remaining < 0 or i == len(coins):           # L2: O(1) base: overshoot or no coins left
            return 0
        return f(i, remaining - coins[i]) + f(i + 1, remaining)  # L3: use coin or skip
    return f(0, amount)

TypeScript

function change(amount: number, coins: number[]): number {
    function f(i: number, remaining: number): number {
        if (remaining === 0) return 1;                              // L1: O(1) base: made amount
        if (remaining < 0 || i === coins.length) return 0;        // L2: O(1) base: overshoot/done
        return f(i, remaining - coins[i]) + f(i + 1, remaining);  // L3: use coin or skip
    }
    return f(0, amount);
}

Swift

final class Solution {
    func change(_ amount: Int, _ coins: [Int]) -> Int {
        func solve(_ index: Int, _ remaining: Int) -> Int { if remaining == 0 { return 1 }; if index == coins.count || remaining < 0 { return 0 }; return solve(index, remaining - coins[index]) + solve(index + 1, remaining) }
        return solve(0, amount)
    }
}

Where the time goes, line by line

Variables: n = len(coins), A = amount.

Line	Per-call cost	Times executed	Contribution
L1-L2 (base cases)	$O(1)$	once per leaf	$O(1)$ each
L3 (two recursive calls)	$O(1)$ work + 2 calls	every non-leaf	$O(2^{n+A})$ ← dominates

Without memoization, the same (i, remaining) is recomputed many times across branches of the call tree.

Complexity

• Time: $O(2^{n+A})$ worst case, driven by L3 double-branching.
• Space: $O(n + A)$ recursion depth.

Approach 2: Top-down memoized

Cache by (i, remaining).

Python

from functools import lru_cache

def change(amount, coins):
    @lru_cache(maxsize=None)                            # L1: cache decorator
    def f(i, remaining):
        if remaining == 0:                              # L2: O(1) base case
            return 1
        if remaining < 0 or i == len(coins):           # L3: O(1) base case
            return 0
        return f(i, remaining - coins[i]) + f(i + 1, remaining)  # L4: O(1) with cache
    return f(0, amount)

TypeScript

function change(amount: number, coins: number[]): number {
    const memo: Map<string, number> = new Map();
    function f(i: number, remaining: number): number {
        if (remaining === 0) return 1;                             // L2: O(1) base case
        if (remaining < 0 || i === coins.length) return 0;       // L3: O(1) base case
        const key = `${i},${remaining}`;
        if (memo.has(key)) return memo.get(key)!;                 // L1: O(1) cache lookup
        const result = f(i, remaining - coins[i]) + f(i + 1, remaining);  // L4: cached
        memo.set(key, result);
        return result;
    }
    return f(0, amount);
}

Where the time goes, line by line

Variables: n = len(coins), A = amount.

Line	Per-call cost	Times executed	Contribution
L1 (lru_cache)	$O(1)$	1	$O(1)$
L2-L3 (base cases)	$O(1)$	once per unique (i, remaining)	$O(n · A)$ total
L4 (cached calls)	$O(1)$ per call	at most n · (A+1) unique states	$O(n · A)$ ← dominates

Each unique (i, remaining) pair is computed once. There are n * (A+1) such pairs.

Complexity

• Time: $O(n · amount)$, driven by L4 across all unique (i, remaining) states.
• Space: $O(n · amount)$ for the memo table.

Try this approach:

Python

▶ Run Python ↻ Reset

idle

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

TypeScript

▶ Run TS ↻ Reset

idle

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Go

▶ Run Go ↻ Reset

idle

Click Run Go to execute. Runs via the Go Playground API.

Swift

final class Solution {
    func change(_ amount: Int, _ coins: [Int]) -> Int {
        var memo: [String: Int] = [:]
        func solve(_ index: Int, _ remaining: Int) -> Int { if remaining == 0 { return 1 }; if index == coins.count || remaining < 0 { return 0 }; let key = "\(index):\(remaining)"; if let value = memo[key] { return value }; let value = solve(index, remaining - coins[index]) + solve(index + 1, remaining); memo[key] = value; return value }
        return solve(0, amount)
    }
}

Approach 3: Bottom-up 1-D DP with outer loop over coins (canonical)

Think of it as an unbounded knapsack counting problem. The loop order matters: coins outside, amounts inside. Swapping the loops would count permutations instead of combinations.

Python

def change(amount, coins):
    dp = [0] * (amount + 1)    # L1: O(A) table init
    dp[0] = 1                  # L2: O(1) base: one way to make amount 0 (use no coins)
    for c in coins:            # L3: O(n) outer loop over coins
        for s in range(c, amount + 1):   # L4: O(A) inner loop, left-to-right
            dp[s] += dp[s - c]           # L5: O(1) accumulate ways using coin c
    return dp[amount]          # L6: O(1) answer

TypeScript

function change(amount: number, coins: number[]): number {
    const dp: number[] = new Array(amount + 1).fill(0);  // L1: O(A) table init
    dp[0] = 1;                                            // L2: O(1) base: one way for amount 0
    for (const c of coins) {                              // L3: O(n) outer loop over coins
        for (let s = c; s <= amount; s++) {               // L4: O(A) inner loop, left-to-right
            dp[s] += dp[s - c];                           // L5: O(1) accumulate ways
        }
    }
    return dp[amount];                                    // L6: O(1) answer
}

Where the time goes, line by line

Variables: n = len(coins), A = amount.

Line	Per-call cost	Times executed	Contribution
L1-L2 (init)	$O(A)$	1	$O(A)$
L3+L4 (double loop)	$O(1)$ body	n · A	$O(n · A)$ ← dominates
L5 (DP update)	$O(1)$	n · A	included above

The left-to-right inner loop (L4) is what makes this unbounded knapsack (vs. 0/1): when we update dp[s] at step s, dp[s - c] already reflects the current coin c being used, so it can be used multiple times. Contrast with 494 Target Sum (0/1 knapsack) where the inner loop runs right-to-left.

Complexity

• Time: $O(n · amount)$, driven by L3/L4 (the double loop).
• Space: $O(amount)$ for the 1-D DP array.

Why coin-outside, amount-inside

With coin-outside, each coin is “introduced” once; by the time the inner loop finishes, you’ve added every multiset that includes that coin an integer number of times. Amount-outside would multi-count, treating [1, 2] and [2, 1] as different compositions.

Try this approach:

Python

▶ Run Python ↻ Reset

idle

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

TypeScript

▶ Run TS ↻ Reset

idle

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Go

▶ Run Go ↻ Reset

idle

Click Run Go to execute. Runs via the Go Playground API.

Swift

final class Solution {
    func change(_ amount: Int, _ coins: [Int]) -> Int {
        var dp = Array(repeating: 0, count: amount + 1); dp[0] = 1
        for coin in coins where coin <= amount { if coin <= amount { for value in coin...amount { dp[value] += dp[value - coin] } } }; return dp[amount]
    }
}

Summary

Approach	Time	Space
Naive recursion	$O(2^{n+A})$	$O(n + A)$
Top-down memo	$O(n · amount)$	$O(n · amount)$
1-D DP, coin-outside	$O(n · amount)$	$O(amount)$

Template for every “count combinations using unlimited items” problem (Number of Ways to Write N as Sum of Powers, etc.).

Test cases

Python

# Quick smoke tests, paste into a REPL or save as test_518.py and run.
# Uses the canonical implementation (Approach 3: 1-D DP, coin-outside).

def change(amount, coins):
    dp = [0] * (amount + 1)
    dp[0] = 1
    for c in coins:
        for s in range(c, amount + 1):
            dp[s] += dp[s - c]
    return dp[amount]

def _run_tests():
    # problem statement examples
    assert change(5, [1, 2, 5]) == 4
    assert change(3, [2]) == 0
    # edge: amount = 0 (one way: use nothing)
    assert change(0, [1, 2, 5]) == 1
    # single coin exactly divides amount (only one combination: 5+5)
    assert change(10, [5]) == 1
    # larger case
    assert change(10, [1, 5, 10]) == 4
    print("all tests pass")

if __name__ == "__main__":
    _run_tests()

TypeScript

function change(amount: number, coins: number[]): number {
    const dp: number[] = new Array(amount + 1).fill(0);
    dp[0] = 1;
    for (const c of coins)
        for (let s = c; s <= amount; s++)
            dp[s] += dp[s - c];
    return dp[amount];
}

console.assert(change(5, [1, 2, 5]) === 4);
console.assert(change(3, [2]) === 0);
console.assert(change(0, [1, 2, 5]) === 1);
console.assert(change(10, [5]) === 1);
console.assert(change(10, [1, 5, 10]) === 4);
console.log("all tests pass");

Related data structures

• Arrays, DP indexed by subtotal

Related concepts

• Knapsack Patterns, the choose or skip structure behind capacity, target, and subset states.
• Dynamic Programming, the state and transition model for reusing answers to overlapping subproblems.