Coin Change II — InterviewPrepKit

Solving tips

Recognize this as an unbounded (counting) knapsack: dp[i][a] = number of ways to make amount a using the first i coin types, summing 'skip this type' + 'use one more of this type'.
Process coin TYPES in the outer loop to count combinations (order-insensitive); putting the amount loop outside instead counts ordered permutations (that is Combination Sum IV) and overcounts.
Target O(coins x amount) time and O(amount) space with a 1-D array; iterate amount ASCENDING to encode unlimited reuse (descending would give the 0/1 'each coin once' semantics).
Pitfall: forgetting to seed dp[0]=1 (the empty combination) — without it every count collapses to 0.

Problem

You are given an integer amount and an array coins of distinct coin denominations. You have an unlimited supply of each coin. Return the number of distinct combinations of coins that sum exactly to amount.

Two combinations are the same if they use the same multiset of coins — order does not matter (1 + 2 and 2 + 1 count once). If no combination works, return 0.

Examples

amount = 5, coins = [1, 2, 5] → 4 — the combinations are 5, 2+2+1, 2+1+1+1, 1+1+1+1+1.
amount = 3, coins = [2] → 0 — you can only ever make even totals.
amount = 0, coins = [7] → 1 — the single empty combination makes 0.

Constraints

1 <= coins.length <= 300
1 <= coins[i] <= 5000, all denominations distinct
0 <= amount <= 5000
The answer fits in a signed 32-bit integer.

An exponential enumeration of every combination blows up; you need a polynomial O(coins × amount) DP.

Think about it first

Hint 1

Because order does not matter, fix an order on the coin *types* and decide them one type at a time. That prevents counting `1+2` and `2+1` as different — you always "consider coin 1's usage, then coin 2's usage."

Hint 2

Make one axis "how many coin types you are allowed to use so far" and the other axis "the amount you still need." `dp[i][a]` = number of ways to form amount `a` using only the first `i` coin types.

Hint 3

For coin type `i` and amount `a`: either you don't use coin `i` at all (`dp[i-1][a]`), or you use at least one copy and stay on the same row because supply is unlimited (`dp[i][a - coins[i-1]]`). Base case: `dp[i][0] = 1`.

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

Intuition: 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.

class Solution:
    def change(self, 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.

Why the constraints kill it: with amount up to 5000 and 300 coin types the unmemoized tree revisits the same (i, rem) pairs enormously many times.

Approach 2 — Top-down memoization

The insight: the only arguments that vary are (i, rem) — at most (n+1) × (amount+1) pairs. Cache them and the exponential tree becomes a filled 2-D grid.

from functools import lru_cache


class Solution:
    def change(self, 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

The insight: 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.

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

class Solution:
    def change(self, 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

The insight: 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 makes a single 1-D array hold both correctly — the left cell is this row’s value, the current cell still holds last row’s value before being overwritten. Iterating ascending (not descending) is exactly what encodes unlimited reuse.

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]

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.