Introduction

The classic coin combinations problem asks how many distinct ways you can make a target amount using a given set of coin denominations. It is a standard dynamic programming problem because the number of ways to make a larger amount depends on the number of ways to make smaller amounts.

What Problem Are We Actually Solving

There are two closely related coin problems:

• minimum number of coins needed to reach an amount
• number of combinations that can reach an amount

This article is about the second one: counting combinations.

For example, with coins [1, 2, 5] and amount 5, the valid combinations are:

• '5'
• '2 + 2 + 1'
• '2 + 1 + 1 + 1'
• '1 + 1 + 1 + 1 + 1'

That means the answer is 4.

Why Order Usually Should Not Matter

In the combination version of the problem, 2 + 1 + 1 + 1 is the same combination as 1 + 2 + 1 + 1. We count them once.

This matters because the dynamic programming loop order determines whether you count:

• combinations
• or ordered sequences, sometimes called permutations

To count combinations correctly, iterate over coins first and amounts second.

A One-Dimensional Dynamic Programming Solution

The standard solution uses an array dp where dp[x] means "number of ways to make amount x."

1def count_combinations(coins, amount):
2    dp = [0] * (amount + 1)
3    dp[0] = 1
4
5    for coin in coins:
6        for x in range(coin, amount + 1):
7            dp[x] += dp[x - coin]
8
9    return dp[amount]
10
11
12print(count_combinations([1, 2, 5], 5))

The output is:

4

This works because each coin updates the number of ways to build later amounts without double-counting different orderings of the same combination.

Why the Recurrence Works

When processing a coin, say 2, any way to make amount x - 2 can be extended by one 2 coin to make amount x.

So the update rule is:

dp[x] += dp[x - coin]

The base case is:

dp[0] = 1

There is exactly one way to make zero amount: choose no coins.

Everything else builds from that foundation.

Step-by-Step Example

Take coins = [1, 2, 5] and amount = 5.

Initial state:

dp = [1, 0, 0, 0, 0, 0]

After coin 1:

dp = [1, 1, 1, 1, 1, 1]

After coin 2:

dp = [1, 1, 2, 2, 3, 3]

After coin 5:

dp = [1, 1, 2, 2, 3, 4]

So dp[5] = 4.

That final entry is the answer.

A Recursive Version with Memoization

If you prefer top-down logic, memoization also works.

1from functools import lru_cache
2
3
4def count_combinations_recursive(coins, amount):
5    coins = tuple(coins)
6
7    @lru_cache(maxsize=None)
8    def solve(i, remaining):
9        if remaining == 0:
10            return 1
11        if remaining < 0 or i == len(coins):
12            return 0
13
14        use_coin = solve(i, remaining - coins[i])
15        skip_coin = solve(i + 1, remaining)
16        return use_coin + skip_coin
17
18    return solve(0, amount)
19
20
21print(count_combinations_recursive([1, 2, 5], 5))

This version is often easier to explain conceptually, though the iterative DP is usually more memory-efficient.

Time and Space Complexity

For the iterative dynamic programming approach:

• time complexity is O(number_of_coins * amount)
• space complexity is O(amount)

That is efficient enough for many practical constraints and is the main reason this solution is so popular in interviews and programming contests.

Variations of the Problem

Be careful about which variant you are solving. Common variations include:

• finite supply of each coin
• minimum coin count instead of number of combinations
• counting ordered sequences instead of unordered combinations

Each variation changes the recurrence or loop order.

That is why copying a coin-change solution blindly can produce the wrong answer even when the code looks reasonable.

Common Pitfalls

A common mistake is iterating amounts before coins, which turns the solution into counting ordered arrangements instead of combinations.

Another issue is forgetting the base case dp[0] = 1. Without it, nothing can build upward correctly.

Developers also sometimes confuse the count-combinations problem with the minimum-coins problem. They are related but not the same dynamic program.

Finally, if coin denominations include duplicates, you may need to deduplicate them first depending on the exact problem statement.

Summary

• The coin combinations problem counts ways to form an amount, not the minimum coin count.
• The standard dynamic programming solution uses dp[x] += dp[x - coin].
• Iterate over coins first to count combinations correctly.
• 'dp[0] = 1 is the crucial base case.'
• The usual time complexity is O(coins * amount) with O(amount) space.