Coin Change II

We count combinations (not permutations) of coins that sum to amount. Each coin can be used an unlimited number of times. Select an approach to visualize:

At each call dfs(i, a) we decide: skip coin i (move to i+1) or use coin i (stay at i, reduce amount). Sum both paths.

1. 1Base case: if a == 0, we found a valid combination — return 1.
2. 2Base case: if i ≥ len(coins), no coins left — return 0.
3. 3Skip coin i: call dfs(i+1, a).
4. 4Use coin i (if a ≥ coins[i]): call dfs(i, a-coins[i]).
5. 5Return skip + use. Many subproblems are recomputed — fixed by memoization.

class Solution:
    def change(self, amount, coins):
        coins.sort()
        def dfs(i, a):
            if a == 0: return 1
            if i >= len(coins): return 0
            res = 0
            if a >= coins[i]:
                res = dfs(i + 1, a)
                res += dfs(i, a - coins[i])
            return res
        return dfs(0, amount)

The recursion recomputes the same (i, a) states many times. There are onlyn × (amt+1) unique states. Cache each result in memo to avoid repeated work.

1. 1Initialize memo[i][a] = -1 for all states.
2. 2At the start of each call, if memo[i][a] != -1, return the cached value.
3. 3Compute normally, then store in memo[i][a] before returning.
4. 4Unique computations drop from exponential to O(n · amount).

class Solution:
    def change(self, amount, coins):
        n = len(coins)
        memo = [[-1]*(amount+1) for _ in range(n+1)]
        def dfs(i, a):
            if a == 0: return 1
            if i >= n: return 0
            if memo[i][a] != -1: return memo[i][a]
            res = 0
            if a >= coins[i]:
                res = dfs(i + 1, a)
                res += dfs(i, a - coins[i])
            memo[i][a] = res
            return res
        return dfs(0, amount)

dp[i][a] = number of ways to make amount a using coins coins[i..n-1]. Base case: dp[i][0] = 1 for all i (one way to make 0 — use nothing).

1. 1Initialize all dp[i][0] = 1. All other cells start at 0.
2. 2Iterate i from n-1 down to 0.
3. 3For each amount a: dp[i][a] = dp[i+1][a] (skip coin) + dp[i][a-coins[i]] (use coin, if a ≥ coins[i]).
4. 4Answer: dp[0][amount].

class Solution:
    def change(self, amount, coins):
        n = len(coins)
        dp = [[0]*(amount+1) for _ in range(n+1)]
        for i in range(n+1): dp[i][0] = 1
        for i in range(n-1, -1, -1):
            for a in range(amount+1):
                if a >= coins[i]:
                    dp[i][a] = dp[i+1][a]
                    dp[i][a] += dp[i][a-coins[i]]
                else:
                    dp[i][a] = dp[i+1][a]
        return dp[0][amount]

Each row of the 2D table only depends on the row below it (dp[i+1]) and itself (dp[i]). Use two 1D arrays: dp (previous row) and nextDP(current row being computed).

1. 1Init dp = [1, 0, 0, ..., 0]. This represents the bottom row.
2. 2For each coin (bottom to top): create nextDP = [1, 0, ..., 0].
3. 3For each amount a: nextDP[a] = dp[a] + nextDP[a - coin] (if valid).
4. 4After each coin, swap: dp = nextDP.

class Solution:
    def change(self, amount, coins):
        dp = [0]*(amount+1); dp[0]=1
        for i in range(len(coins)-1, -1, -1):
            nextDP = [0]*(amount+1); nextDP[0]=1
            for a in range(1, amount+1):
                nextDP[a] = dp[a]
                if a - coins[i] >= 0:
                    nextDP[a] += nextDP[a - coins[i]]
            dp = nextDP
        return dp[amount]

For combination count (not permutation), we can use a single 1D array updated in-place. Iterating left-to-right within each coin ensures each combination is counted once.

1. 1Init dp = [1, 0, 0, ..., 0]. Base: 1 way to make 0.
2. 2For each coin (in any order): iterate amounts from 1 to amount.
3. 3For each a: if coins[i] ≤ a, add dp[a - coins[i]] to dp[a].
4. 4The left-to-right scan allows reusing the same coin multiple times (unbounded knapsack).

class Solution:
    def change(self, amount, coins):
        dp = [0]*(amount+1); dp[0]=1
        for i in range(len(coins)-1, -1, -1):
            for a in range(1, amount+1):
                dp[a] += dp[a-coins[i]] if coins[i] <= a else 0
        return dp[amount]