LeetCode 322 - Coin Change

This Medium problem asks for the minimum number of coins needed to make a target amount. I reduced the remaining amount recursively and stored each result in a memo so the same state would not be calculated repeatedly.

---

Problem link and explanation

• Problem: 322. Coin Change
• Summary: Given an integer array coins and an integer amount, return the minimum number of coins needed to make that amount. Each coin can be used multiple times. Return -1 if the amount cannot be made.

For example, if coins is [1, 2, 5] and amount is 11, the answer is 3 because 5 + 5 + 1 makes 11. Finding one valid combination is not enough. The solution must choose the combination with the fewest coins.

---

Approach

The DFS state is the amount still left to make, represented by remain. At each step, I subtract each available coin and recursively calculate the minimum number of coins needed for the smaller amount.

for coin in coins:
    min_result = min(
        min_result,
        self.dfs(coins, memo, remain - coin),
    )

If remain reaches 0, the amount has been formed exactly, so no additional coins are needed. If it becomes negative, that path cannot form the target amount and returns infinity.

if remain == 0:
    return 0
if remain < 0:
    return float('inf')

When a recursive call finds a valid result, the current coin adds one to the count. The result is stored under remain, and a later call for the same amount returns the cached value instead of searching again.

if remain in memo:
    return memo[remain]

memo[remain] = (
    min_result
    if min_result == float('inf')
    else min_result + 1
)

With [1, 2, 5], the state remain = 6 can be reached through multiple coin sequences. Without memoization, every path recalculates the full subtree below 6. With the memo, each remaining amount is solved once.

---

Troubleshooting

Returning -1 directly from an impossible recursive state would break the minimum comparison. Since -1 is smaller than every valid coin count, an invalid branch could be selected as the best result.

I used infinity for impossible states inside the recursion instead. Infinity will not win a minimum comparison against a valid count, and a state remains infinite only when every available coin leads to another impossible state. The conversion to the -1 required by LeetCode happens once at the outer coinChange boundary.

result = self.dfs(coins, {}, amount)
return result if result != float('inf') else -1

The original complexity comment in the solution described exponential recursion, which applies before memoization. This implementation does not recalculate the same positive remain, so its complexity depends on the number of remaining-amount states and the number of coin types.

---

Complexity analysis

• Time complexity: O(amount × k)
  • States from 0 through amount are memoized, and each state checks all k coin types.
• Space complexity: O(amount)
  • The memo stores a result for each remaining amount, and the recursion stack can also grow proportionally to amount in the worst case.

---

Implementation code

from typing import Dict, List

class Solution:
    def dfs(
        self,
        coins: List[int],
        memo: Dict[int, int],
        remain: int,
    ) -> int:
        if remain == 0:
            return 0
        if remain < 0:
            return float('inf')
        if remain in memo:
            return memo[remain]

        min_result = float('inf')

        for coin in coins:
            min_result = min(
                min_result,
                self.dfs(coins, memo, remain - coin),
            )

        memo[remain] = (
            min_result
            if min_result == float('inf')
            else min_result + 1
        )
        return memo[remain]

    def coinChange(self, coins: List[int], amount: int) -> int:
        result = self.dfs(coins, {}, amount)
        return result if result != float('inf') else -1

---

Summary and reflection

The repeated state in this problem is the remaining amount, not the complete sequence of coins chosen so far. Once two paths reach the same remain, the minimum number of additional coins needed from that point is identical, so the result can be cached by that value.

Plain DFS repeats the same work through many paths. Memoization preserves the recursive structure while reducing the search to one calculation per remaining amount, turning it into a top-down dynamic programming solution.