518. Coin Change II

Problem¶

Count the combinations of unlimited coins that sum to amount. Coin order does not matter.

amount = 5, coins = [1, 2, 5] -> 4 combinations

Key trick¶

Process coins in the outer loop and amounts in ascending order. This counts each combination once while allowing repeated use of the current coin.

Trap¶

Looping over amounts first counts different orders of the same coins separately. The base case is one way to make zero: choose no coins.

Why is it interesting?¶

Changing the loop order in a one-dimensional dynamic program changes whether it counts combinations or ordered sequences.

Python solution¶

class Solution:
    def change(self, amount: int, coins: list[int]) -> int:
        # dp[a] counts combinations totaling a using coins processed so far.
        dp = [0] * (amount + 1)
        dp[0] = 1

        for coin in coins:
            # Ascending amounts allow this coin to be used more than once.
            for a in range(coin, amount + 1):
                dp[a] += dp[a - coin]

        return dp[amount]

Time: \(O(\text{amount} \cdot |\text{coins}|)\). Space: \(O(\text{amount})\).

Comment on my solution¶

Your amount-first loop counts coin orders separately: for amount = 3 and coins = [1, 2], it returns 4 rather than 2. The coins are already unique, so seen does not help; multiplying by dp[coin] also does not represent a valid combination-counting step.

# Ideas:
# - dp[a] = number of coin combination that sum to a
# - I don't see how to solve this

# WRONG
class Solution:
    def change(self, amount: int, coins: list[int]) -> int:
        dp = [0] * (amount + 1)
        dp[0] = 1
        for a in range(1, amount + 1):
            seen = set()
            for coin in coins:
                if a - coin >= 0 and dp[a - coin] and coin not in seen:
                    seen.add(coin)
                    dp[a] += dp[a - coin] * (dp[coin] or 1)
        return dp[amount]

Solution().change(5, [1,2,5])