Coin Change II Solution

Problem

Given a list of coin denominations and a target amount, count the number of distinct ways to combine coins that sum exactly to the target. Each denomination may be used any number of times, and two selections that contain the same coins in different orders count as one combination.

Input: coins = [1, 2, 5], amount = 5
Output: 4
Explanation: The four valid combinations are [1,1,1,1,1], [1,1,1,2], [1,2,2], and [5].

Note that [1,2,2] and [2,2,1] represent the same combination and are counted only once.

Intuition

The problem asks for the number of unordered groupings of coins that reach the target. The key is to process one denomination at a time: after fully accounting for coin i, we move permanently to coin i+1. This fixes a canonical left-to-right ordering so that the same coin set can never be counted twice from different starting points. A 1D DP table that grows the combination count for each reachable amount as new denominations are introduced implements this directly.

Approach 1 — Top-Down Memoization

For each coin index, branch into two sub-problems: skip this denomination and advance to the next, or spend one copy of the current coin and stay at the same index (allowing unlimited reuse). Memoize by (coin index, remaining amount) to avoid recomputing overlapping sub-problems.

Steps:

Define count_ways(coin_index, remaining) — combinations using only coins[coin_index:] that sum to remaining.
Base case: remaining == 0 → return 1 (found one valid combination).
Base case: remaining < 0 or coin_index == len(coins) → return 0 (dead end).
Branch: skip this coin count_ways(coin_index + 1, remaining) or spend one more count_ways(coin_index, remaining - coins[coin_index]).
Cache and return the sum of both branches.
Call count_ways(0, amount).

1from functools import lru_cache
2
3def change(amount: int, coins: list[int]) -> int:
4    @lru_cache(maxsize=None)
5    def count_ways(coin_index: int, remaining: int) -> int:
6        if remaining == 0:
7            return 1
8        if remaining < 0 or coin_index == len(coins):
9            return 0
10        # skip this denomination or spend one more of it
11        return (count_ways(coin_index + 1, remaining)
12                + count_ways(coin_index, remaining - coins[coin_index]))
13
14    return count_ways(0, amount)

Time: O(n × amount) — each unique (coin index, remaining amount) pair is computed exactly once
Space: O(n × amount) — the memo table has one cell per sub-problem, plus O(n) recursion depth

Approach 2 — Bottom-Up 1D DP

Maintain a 1D table where dp[j] holds the number of combinations that sum to j. Introduce one coin at a time and sweep left-to-right, which lets each denomination contribute any number of times within a single pass — and the coin-first outer loop ensures every combination is counted in exactly one canonical order.

Steps:

Allocate dp of size amount + 1, initialized to 0.
Set dp[0] = 1 — exactly one way to reach 0: use no coins.
For each coin denomination, iterate j from coin to amount:
Add dp[j - coin] to dp[j] — each way to reach j - coin can be extended by one more of this coin.
After all denominations are processed, return dp[amount].

1def change(amount: int, coins: list[int]) -> int:
2    dp = [0] * (amount + 1)
3    dp[0] = 1  # one way to reach 0: use no coins
4
5    for coin in coins:
6        for j in range(coin, amount + 1):
7            dp[j] += dp[j - coin]  # extend each combination that already reaches j - coin
8
9    return dp[amount]

Time: O(n × amount) — for each of the n coins, the entire dp array is scanned once
Space: O(amount) — only a single 1D array of size amount + 1 is needed

Complexity Summary

Approach	Time	Space	When to use
Top-down memoization	O(n × amount)	O(n × amount)	When thinking recursively or when only a fraction of states will be visited
Bottom-up 1D DP	O(n × amount)	O(amount)	Interview standard — minimal space, no recursion overhead or stack risk

Common Mistakes

Swapping the loop order — putting amount as the outer loop and coins as the inner loop counts ordered sequences (permutations), so [1,2] and [2,1] are tallied separately. The coin-first outer loop commits to one canonical denomination order and eliminates this double-counting.
Initializing dp[0] = 0 — every count in the table propagates from dp[0] = 1. Without this base case the entire table stays zero and the function always returns 0.
Using a backward inner loop — decrementing j from amount down to coin (the 0/1 knapsack pattern used in Partition Equal Subset Sum) prevents any denomination from being reused in the same pass. This problem allows unlimited reuse, so the forward sweep is required.
Confusing with Coin Change I — that problem minimizes the number of coins used (dp[j] = min(dp[j], dp[j - coin] + 1)); this one counts distinct combinations (dp[j] += dp[j - coin]). The recurrences look similar but are completely different in meaning and initialization.
Missing the loop-order insight under interview pressure — if asked to count permutations instead of combinations, a single loop swap is the entire change. Knowing why the outer loop is over coins (not amounts) is the core insight examiners probe after you give the solution.

Coin Change II — Solution