Chapter 7: Counting the Ways - Coin Change 2

In the last chapter, we solved an optimization problem: finding the fewest coins to make an amount. Now, we'll explore a related but distinct problem that focuses on combinatorics: counting how many unique ways there are to make an amount.

This might seem like a small change, but it requires a different way of thinking to avoid overcounting. LeetCode's "Coin Change 2" (Problem #518) is the perfect problem to illustrate this. It forces us to distinguish between permutations (like [1, 2] and [2, 1]) and combinations (where [1, 2] is counted only once).

The Problem:

You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money.

Return the number of combinations that make up that amount. If that amount of money cannot be made up by any combination of the coins, return 0.

You may assume that you have an infinite number of each kind of coin. The answer is guaranteed to fit into a signed 32-bit integer.

For example:

• coins = [1, 2, 5], amount = 5 -> The answer is 4.

  • The combinations are:

    • 5

    • 2 + 2 + 1

    • 2 + 1 + 1 + 1

    • 1 + 1 + 1 + 1 + 1

Approach 1: The Recursive Solution

Our first instinct might be to adapt the previous recursive solution. However, if we simply sum up the results, we will count permutations instead of combinations. For amount = 3 and coins = [1, 2], we would count 1 + 2 and 2 + 1 as two separate solutions.

To solve this, we must enforce an order on the coins we use. A common technique is to process the coins in a fixed sequence. We'll add an index parameter to our recursive function. At each step, we have two choices for the coin at coins[index]:

1. Use the coin: We use coins[index] and solve for the subproblem amount - coins[index], staying at the same index (since we can use the coin multiple times).

2. Skip the coin: We don't use coins[index] and move on to the next coin by solving for the subproblem with index + 1.

The total number of combinations is the sum of the results from these two choices.

from typing import List

def change_recursive(amount: int, coins: List[int]) -> int:

    def solve(index, current_amount):
        # Base case: We've successfully made the amount.
        if current_amount == 0:
            return 1

        # Base cases: We've run out of coins or overshot the amount.
        if index >= len(coins) or current_amount < 0:
            return 0

        # Choice 1: Use the coin at coins[index]
        use_it = solve(index, current_amount - coins[index])

        # Choice 2: Skip the coin at coins[index]
        skip_it = solve(index + 1, current_amount)

        return use_it + skip_it

    return solve(0, amount)

# Trying it out
# print(change_recursive(5, [1, 2, 5])) # Output: 4
# print(change_recursive(500, [1,2,5,10,20,50])) # Very, very slow

This approach correctly finds the number of combinations, but its performance is terrible due to the explosion of recursive calls on overlapping subproblems (e.g., solve(2, 50) would be called from many different paths).

Approach 2: Memoization with a Decorator (Top-Down DP)

The state of our recursion is defined by two variables: index and current_amount. This is a perfect candidate for memoization. We can cache the result of solve(index, current_amount) to avoid recomputing it.

import functools
from typing import List

class Solution:
    def change_memoized(self, amount: int, coins: List[int]) -> int:

        @functools.lru_cache(maxsize=None)
        def solve(index, current_amount):
            if current_amount == 0:
                return 1

            if index >= len(coins) or current_amount < 0:
                return 0

            use_it = solve(index, current_amount - coins[index])
            skip_it = solve(index + 1, current_amount)

            return use_it + skip_it

        return solve(0, amount)

# Trying it out
# solver = Solution()
# print(solver.change_memoized(500, [1,2,5,10,20,50])) # Instant!

With caching, our clear recursive logic becomes highly efficient. It solves the problem by exploring the decision tree while pruning branches that have already been computed.

Approach 3: Iteration (Bottom-Up DP)

The bottom-up solution for this problem is particularly elegant. We can solve it with a 1D dp array, where dp[i] stores the number of ways to make amount i.

1. Create a dp array of size amount + 1, initialized to all zeros.

2. Set the base case: dp[0] = 1. There is exactly one way to make an amount of 0 (by using no coins).

3. Now, the crucial part: to avoid counting permutations, we iterate through the coins first, and for each coin, we update the dp array.

4. For each coin in coins:

   • Iterate from coin up to amount. For each i, we can form i by adding the current coin to a previously formed amount, i - coin.

   • So, we add the number of ways to make i - coin to our current count for i: dp[i] += dp[i - coin].

By iterating through coins on the outer loop, we ensure that we build up the combinations in a fixed order (e.g., we first find all combinations using only 1s, then all combinations using 1s and 2s, and so on).

def change_iterative(amount: int, coins: List[int]) -> int:
    dp = [0] * (amount + 1)
    dp[0] = 1

    for coin in coins:
        for i in range(coin, amount + 1):
            dp[i] += dp[i - coin]

    return dp[amount]

# Trying it out
# print(change_iterative(5, [1, 2, 5])) # 4

This bottom-up approach is the most efficient and concise solution. It neatly solves the combination vs. permutation issue with its nested loop structure.

Conclusion

This chapter demonstrated a critical concept: how to adapt a DP solution from an optimization goal (min or max) to a counting goal (sum). The key to counting combinations was enforcing an order of operations, which we achieved by passing an index in our recursive solution and by structuring our loops carefully in the iterative one. This pattern is fundamental for a wide range of combinatorial problems.