Coding interview problems › Dynamic Programming

🪙 Dynamic Programming Medium

Coin Change II (Number of Ways)

Coin Change II explained: count the combinations of coins that make an amount, why the loop order matters, O(n·amount) DP in tested Python, with a live visual.

Also searched as: coin change number of ways · count combinations of coins to make amount · unbounded knapsack counting

🪙

Try it live Free

Coin Change (DP)

In the Coin Change lab, watch dp[] fill left to right with each cell built from earlier cells; here each cell adds earlier counts instead of taking a minimum.

Also useful: 0/1 Knapsack (DP)

Open the playground →

The problem

Given coin denominations (unlimited supply of each) and an amount, count how many different combinations of coins add up to it. Order does not matter: 1+2 and 2+1 are the same combination.

Inputamount = 5, coins = [1, 2, 5]
Output4

5, 2+2+1, 2+1+1+1, 1+1+1+1+1

Inputamount = 3, coins = [2]
Output0

The key insight

To count combinations rather than orderings, decide coins one denomination at a time. Process coin c and update ways[a] += ways[a - c] for every amount. Because each coin is fully processed before the next, every combination is built in one fixed coin order, so it is counted exactly once.

Brute force first: Recursively choosing how many of each coin to use works but explores an exponential number of branches.

Step-by-step approach

  1. Create ways of size amount + 1 with ways[0] = 1 (one way to make 0: use nothing).
  2. Loop over coins in the outer loop.
  3. For each coin c, loop a from c up to amount and add ways[a - c] to ways[a].
  4. Going upward lets the same coin be reused any number of times.
  5. Return ways[amount].

Python solution

PYTHON 3tested
def change(amount, coins):
    ways = [1] + [0] * amount      # ways[a] = combinations making a
    for c in coins:                # coins OUTSIDE: counts combinations
        for a in range(c, amount + 1):
            ways[a] += ways[a - c]
    return ways[amount]

Complexity

TimeO(n · amount)
SpaceO(amount)

Each of the n coins sweeps the table of amount + 1 cells once.

Common mistakes

Frequently asked questions

What is the time and space complexity of Coin Change II?

O(number of coins × amount) time and O(amount) space with the 1D table.

Why does the loop order matter in Coin Change II?

With coins in the outer loop, each combination is assembled in a fixed coin order and counted once. With amounts in the outer loop, every ordering of the same coins is counted, which answers a different question (number of ordered sequences).

How is this related to unbounded knapsack?

It is the counting version of unbounded knapsack: each item (coin) can be used any number of times, which is why the inner loop runs upward.

Preparing for placements?

Take the 2-minute readiness check to find your weak patterns, then follow the placement path from DSA core to system design.

📋 2-minute readiness check The full placement path

All coding interview problems More Dynamic Programming Coin Change (DP) lab Placement prep guides

Problem statements on this site are written in our own words. Problem names are the common names used across interview-prep communities; BitBootcamp is an independent learning platform and is not affiliated with LeetCode or any company that asks these questions.