Generated by Codex with GPT-5

Quick facts

• Difficulty: MEDIUM
• Problem: Coin Change II
• Main tags: Array, Dynamic Programming

What the problem is really asking

The input gives a target amount and a list of coin denominations. Each denomination can be used as many times as needed.

The task is to count how many distinct combinations can make the amount exactly. It is not asking for the minimum number of coins, and it is not asking whether the amount is possible at all.

The subtle part is that order does not matter. For example, if the amount is 5 and the coins are [1, 2, 5], then 1 + 2 + 2 is the same combination no matter which order those coins are written in. That detail completely determines the right dynamic programming setup.

The clean DP idea

A good first state is:

ways[i][a] = number of ways to make amount a using the first i coin types

For each coin type, there are only two meaningful choices:

• do not use this coin at all
• use it at least once

If the current coin value is coin, then the recurrence is:

ways[i][a] = ways[i - 1][a] + ways[i][a - coin]

The first term means “skip this coin type.” The second term means “use this coin once, and then solve the remaining amount while still being allowed to use the same coin again.”

That recurrence is the heart of the problem because it matches the unlimited-use rule exactly.

Why the 1D optimization works

The full 2D table is easy to reason about, but the optimal implementation only needs one array.

Let ways[a] mean:

the number of combinations to make amount a using only the coin types processed so far

Start with:

• ways[0] = 1 because there is exactly one way to make amount zero: choose nothing
• every other entry starts at 0

Then process the coin types one by one. For each coin, scan amounts from coin up to target_amount in increasing order:

ways[current_amount] += ways[current_amount - coin]

This works because while processing one coin type, ways[current_amount - coin] already represents combinations that may use the same coin repeatedly, which is exactly what this problem allows.

Why loop order matters so much

The outer loop must go over coins first.

That is what prevents counting the same combination multiple times in different orders. Once the algorithm starts processing coin 2, it builds new combinations by extending combinations that were already formed using only earlier coin types plus 2 itself. It never revisits the same set of coins in a different order later.

If the loops were reversed and amounts were processed first, the algorithm would start counting permutations instead of combinations. That is one of the most common interview mistakes on this problem.

How to derive this in an interview

A practical derivation goes like this:

1. Start with a recursion that decides how many copies of the current coin to use.
2. Notice that the same pair of ideas keeps repeating: which coin types are still allowed, and how much amount is left.
3. Turn that repeated work into dynamic programming with a state based on coin index and remaining amount.
4. Observe that the 2D recurrence only needs the previous row and the current row’s earlier values.
5. Compress it to one dimension without changing the meaning of the state.

That path shows the interviewer that the final one-array solution is not a memorized trick. It falls naturally out of the more explicit 2D definition.

Python solution

from typing import Iterable, List


def normalize_denominations(raw_denominations: Iterable[int]) -> list[int]:
    """
    Return sorted, unique, positive coin values.

    LeetCode already provides valid inputs, but normalization keeps the core
    counting logic simple and makes the helper reusable.
    """
    return sorted({value for value in raw_denominations if value > 0})


def count_combinations_to_reach_amount(
    denominations: list[int], target_amount: int
) -> int:
    """
    Return the number of distinct unordered combinations that sum to target_amount.

    Each denomination may be used any number of times.
    """
    if target_amount < 0:
        return 0

    # There is exactly one way to make amount 0: choose no coins.
    ways_to_make_amount = [0] * (target_amount + 1)
    ways_to_make_amount[0] = 1

    for coin_value in denominations:
        # Process one coin type at a time so combinations are counted once,
        # regardless of the order in which the same coins could be arranged.
        for current_amount in range(coin_value, target_amount + 1):
            remaining_amount = current_amount - coin_value
            ways_to_make_amount[current_amount] += ways_to_make_amount[
                remaining_amount
            ]

    return ways_to_make_amount[target_amount]


class Solution:
    def change(self, amount: int, coins: List[int]) -> int:
        normalized_coins = normalize_denominations(coins)
        return count_combinations_to_reach_amount(normalized_coins, amount)

The time complexity is O(number_of_coin_types * amount) because each coin updates each reachable amount once. The space complexity is O(amount) for the one-dimensional DP array.

Interview follow-ups

What changes if each coin can be used at most once?

Then this is no longer an unbounded knapsack-style problem. The state definition can stay similar, but the transition must prevent reusing the same coin more than once. In the one-dimensional version, that means iterating amounts in decreasing order for each coin. Going backward ensures that when the algorithm updates ways[a], it still reads the value from the previous coin set rather than a value already updated by the same coin in the current pass. The time complexity stays O(number_of_coin_types * amount), but the loop direction becomes the key correctness detail.

What if the interviewer wants order to matter?

Then the problem changes from counting combinations to counting permutations. The recurrence must reflect that the last coin placed could be any denomination. A clean one-dimensional definition is ways[a] = number of ordered sequences that sum to a, with ways[0] = 1. In that version, the outer loop goes over amounts and the inner loop goes over coins, because each amount should consider every possible last step. The asymptotic complexity stays the same, but the meaning of the state and the loop order both change.

How would you return the actual combinations instead of just the count?

Once the problem asks for all combinations, the output itself can be exponential, so the goal is no longer just a compact DP count. A common interview answer is depth-first search with backtracking over the coin list, keeping a start index so the combination is built in nondecreasing coin order and duplicates are avoided naturally. That approach is easy to explain and directly matches the “order does not matter” rule. The tradeoff is that generating the full combinations necessarily costs much more than the counting-only version, because the algorithm must explicitly materialize each valid answer.