Introduction

The coin combination problem asks how many different ways you can make a target amount from a set of coin denominations. It is a classic dynamic-programming problem because partial answers get reused many times, and a small change in loop order can completely change what you are counting.

The key word is combinations. In this version, 1 + 2 + 1 and 2 + 1 + 1 are the same answer because order does not matter.

Combination Versus Permutation

Start with a simple example. Suppose the coins are 1, 2, and 3, and the target amount is 4. The valid combinations are:

• '1 + 1 + 1 + 1'
• '1 + 1 + 2'
• '1 + 3'
• '2 + 2'

That is four combinations.

If you counted different orders separately, you would get a larger number. For example, 1 + 3 and 3 + 1 would become two distinct results. That is a different problem, often called counting permutations or ordered sums.

Many bugs come from mixing those two interpretations. Before you write code, decide whether order matters.

Dynamic Programming with a One-Dimensional Array

The standard combination-counting solution uses a one-dimensional DP array:

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

This prints 4.

The meaning of dp[a] is: how many combinations can make amount a using the coin types processed so far. The base case dp[0] = 1 means there is exactly one way to make amount zero: choose no coins.

When the current coin is 2, every amount a can inherit combinations from a - 2. Because the outer loop iterates over coin types, the algorithm counts each combination once instead of counting the same multiset in many different orders.

Why Loop Order Matters

This specific loop order is the core idea:

for coin in coins:
    for amount in range(coin, target + 1):
        dp[amount] += dp[amount - coin]

If you reverse the loops and iterate amounts first, then coins, you start counting ordered sequences instead of combinations. That is sometimes useful, but it answers a different question.

So the algorithm is not just about recurrence relations. It is also about choosing an iteration order that matches the combinatorial meaning you want.

A Recursive Way to Think About It

Dynamic programming is the efficient implementation, but recursion explains the structure. For each denomination, you have two choices:

• use the coin and reduce the remaining amount
• skip the coin and move to the next denomination

With memoization, that recursive definition becomes practical:

1from functools import lru_cache
2
3
4def count_combinations_recursive(coins, target):
5    coins = tuple(coins)
6
7    @lru_cache(maxsize=None)
8    def solve(index, remaining):
9        if remaining == 0:
10            return 1
11        if remaining < 0 or index == len(coins):
12            return 0
13
14        use_it = solve(index, remaining - coins[index])
15        skip_it = solve(index + 1, remaining)
16        return use_it + skip_it
17
18    return solve(0, target)

This version mirrors the mathematical recurrence nicely, but the iterative DP version is usually simpler and uses predictable memory.

Complexity and Scaling

For n coin types and target amount A, the one-dimensional DP solution runs in O(n * A) time and uses O(A) memory. That is efficient enough for many interviews, teaching examples, and real application features such as pricing rules, reward systems, or change calculators.

One practical detail is integer size. The number of combinations can grow quickly, so some languages need big-integer support for large targets.

Common Pitfalls

The most common mistake is counting permutations when the problem asked for combinations. Always test with a tiny example where order would change the answer.

Another mistake is forgetting the base case dp[0] = 1. Without it, every entry stays zero because there is no seed value to build from.

A third issue is accepting zero or negative coin values. The standard recurrence assumes positive denominations.

Some implementations also sort the coin list and then assume sorting is the reason the algorithm works. Sorting can help readability, but the real reason it works is the state definition and loop order.

Summary

• The usual coin problem asks for combinations, not ordered sequences.
• A one-dimensional dynamic-programming array is the simplest efficient solution.
• Set dp[0] = 1 because there is one way to make amount zero.
• Keep coins in the outer loop to avoid double-counting orderings.
• Memoized recursion is good for understanding the recurrence, but iterative DP is usually the best implementation.