TL;DR
Count-combinations DP over (coin type, amount) — O(coins × amount) time, O(amount) space after rolling to one row.
Approach 1 — Brute-force recursion
Walk the coin types in a fixed order. At coin type i with rem left to make, either skip this type entirely, or use one more copy of it and stay at type i since it can be reused. Fixing the order is what stops 1+2 and 2+1 from both being counted.
def change(amount: int, coins: list[int]) -> int:
n = len(coins)
def dfs(i: int, rem: int) -> int:
if rem == 0:
return 1
if i == n or rem < 0:
return 0
skip = dfs(i + 1, rem) # use no more of coin i
take = dfs(i, rem - coins[i]) # use one coin i, stay on type i
return skip + take
return dfs(0, amount)
Complexity: exponential — the recursion branches without bound on rem.
With amount up to 5000 and 300 coin types, the unmemoized tree revisits the same (i, rem) pairs many times over.
Approach 2 — Top-down memoization
The only arguments that vary are (i, rem) — at most (n+1) × (amount+1) pairs. Cache them and the exponential tree collapses into a filled 2-D grid.
from functools import lru_cache
def change(amount: int, coins: list[int]) -> int:
n = len(coins)
@lru_cache(maxsize=None)
def dfs(i: int, rem: int) -> int:
if rem == 0:
return 1
if i == n or rem < 0:
return 0
return dfs(i + 1, rem) + dfs(i, rem - coins[i])
return dfs(0, amount)
Complexity: O(coins × amount) time and space.
Approach 3 — Bottom-up 2-D table
Turn the memo into an explicit grid filled by increasing coin type and amount.
Table meaning: dp[i][a] = number of combinations that sum to a using only the first i coin types.
Each cell depends on the cell directly above it (skip coin i) and the cell to its left by one coin value (use one more coin i):
flowchart LR
A["dp[i-1][a]<br/>skip coin i"] --> C["dp[i][a]"]
B["dp[i][a - coin]<br/>use one coin i"] --> C
2-D recurrence:
dp[0][0] = 1, dp[0][a>0] = 0 # no coins make only the empty sum
dp[i][a] = dp[i-1][a] # ignore coin i
+ dp[i][a - coins[i-1]] # if a >= coins[i-1]: use one more coin i
def change(amount: int, coins: list[int]) -> int:
n = len(coins)
dp = [[0] * (amount + 1) for _ in range(n + 1)]
for i in range(n + 1):
dp[i][0] = 1 # one way to make 0: take nothing
for i in range(1, n + 1):
coin = coins[i - 1]
for a in range(1, amount + 1):
dp[i][a] = dp[i - 1][a]
if a >= coin:
dp[i][a] += dp[i][a - coin]
return dp[n][amount]
Walkthrough on amount = 5, coins = [1, 2, 5]. Column 0 is all 1s. Row for coin 1 fills every amount with exactly 1 way (all-ones). Row for coin 2 adds the even splits: dp[2] = [1, 1, 2, 2, 3, 3]. Row for coin 5 adds the single 5 combination at a = 5: dp[3][5] = dp[2][5] + dp[3][0] = 3 + 1 = 4. Answer 4.
Complexity: O(coins × amount) time, O(coins × amount) space.
Approach 4 — Space-optimized rolling row
Row i reads only row i-1 (via dp[i-1][a]) and its own already-updated cells to the left (via dp[i][a - coin]). Iterating a ascending lets a single 1-D array hold both correctly: the left cell is this row’s value, and the current cell still holds the previous row’s value before being overwritten. Ascending iteration (not descending) is what encodes unlimited reuse.
def change(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]
Walkthrough (same input): after coin 1, dp = [1,1,1,1,1,1]; after coin 2, dp = [1,1,2,2,3,3]; after coin 5, dp[5] += dp[0] → dp = [1,1,2,2,3,4]. Answer dp[5] = 4.
Complexity: O(coins × amount) time, O(amount) space.
Common pitfalls
- Coins loop inside, amount loop outside — swapping the loop order counts ordered sequences (that’s the Combination Sum IV / “number of permutations” problem) and overcounts here. Coin type must be the outer loop.
- Descending amount iteration — that gives the 0/1-knapsack “each coin once” semantics; ascending is required for unlimited supply.
- Forgetting
dp[0] = 1 — the empty combination is the seed that every real combination is built from; without it every answer collapses to 0.
- Handling
amount = 0: the base cases already return 1, which is correct.
Pattern takeaway
Counting combinations (order-insensitive) is the “unbounded knapsack, count paths” template: make coin type one dimension and target amount the other, sum “skip this type” plus “use one more of this type,” and process types in the outer loop so each multiset is generated exactly once. Ascending inner loop = reuse allowed; type-outer = order ignored.