Coin Change II

35 min · change()

Four ways to pay doesn't mean four orders of the same coins. A 2 followed by a 1 buys the same thing as a 1 followed by a 2, so you count that choice once.

You're given distinct coin denominations in coins and a non-negative integer amount. You have an unlimited supply of every coin. Return the number of combinations — selections where order doesn't matter — whose values total exactly amount.

A few ground rules:

Reordering the same selected coins does not create a new combination.
You may use each denomination any number of times.
When amount is 0, the empty selection is one valid combination.

Constraints

1 <= coins.length <= 12
1 <= coins[i] <= 1_000
Every value in coins is distinct.
0 <= amount <= 5_000
The exact combination count is less than 2^31.

Hints

Choose a count per denomination

For one coin value, try using it zero times, once, twice, and so on. Then move to the next denomination with the remaining amount. This never rearranges the same selection into a duplicate.

Give the DP a meaning

Let dp[a] count combinations that make total a using only the coin values you've processed so far. Start with dp[0] = 1 for the empty combination.

The loop order carries the rule

Process one coin in the outer loop. For that coin, walk totals upward and add dp[a - coin] into dp[a]. Locking in coin types this way prevents reordered copies.

Follow-up

What changes if order does matter, so [1, 2] and [2, 1] must count separately?

Visible cases

Examples

Example 1

ready

Input: coins = [ 1, 2, 5 ] amount = 5
Expected: 4
Why: the four selections are 5, 2+2+1, 2+1+1+1, and five 1s

Example 2

ready

Input: coins = [ 2 ] amount = 3
Expected: 0
Why: no number of 2-value coins makes 3

Example 3

ready

Input: coins = [ 10 ] amount = 10
Expected: 1
Why: one 10-value coin is the only combination

Interview signal

Asked at

AmazonGoogle

Enumerate coin counts — one denomination at a time

Depth-first search (DFS) follows one choice path until it finishes, then backs up to try another. Sort the denominations, choose how many copies of the current coin to use, and recurse on the remaining denominations. Because each level owns one coin type, the same selection can never reappear in a different order.

def change(coins: list[int], amount: int) -> int:
    ordered = sorted(coins, reverse=True)
 
    def count(index: int, remaining: int) -> int:
        if index == len(ordered) - 1:
            return int(remaining % ordered[index] == 0)
 
        coin = ordered[index]
        ways = 0
        for used in range(remaining // coin + 1):
            ways += count(index + 1, remaining - used * coin)
        return ways
 
    return count(0, amount)

The search can branch once for every feasible count of every denomination. Time O((amount + 1)^k) as a loose upper bound for k = len(coins). Space O(k) for the recursion stack and sorted coin list.

One-dimensional combinations DP — lock in coin types

Dynamic programming (DP) stores counts for smaller totals so later totals can reuse them. Let dp[a] mean: combinations that make a using only the coin types processed so far. The base case dp[0] = 1 represents choosing nothing.

For each coin, the transition — the rule for updating one DP answer — is:

dp[a] += dp[a - coin]

def change(coins: list[int], amount: int) -> int:
    dp = [0] * (amount + 1)
    dp[0] = 1
 
    for coin in coins:
        for current in range(coin, amount + 1):
            dp[current] += dp[current - coin]
 
    return dp[amount]

The outer coin loop is part of the correctness argument. Once you process a coin, every new combination adds that coin to combinations built from this coin or earlier ones. Swapping the loops would count ordered sequences instead.

Time O(amount · k). Space O(amount) for the DP array.

Loading editor

Console

ready to run

Ready to run.

3 cases are queued.

Visible testcase

Case 1

Arguments · JSON arraycoins: int[] · amount: int

Expected

Run: visible + custom · Submit: full suite