advanced9 min read·Updated October 5, 2026

Coin Change Combinations Explained: Making 5 with [1, 2, 5]

Master coin change combinations where order doesn't matter. Trace the DP table for [1, 2, 5] making 5, build mental models, and avoid counting permutations.

By Learnisim AI·Published October 5, 2026
LEARNING ARCSetup → Model in the example → Full trace → Twist → Edge cases → Apply
PREREQUISITES
  • Basic 1D Dynamic Programming
  • Nested loops
  • Coin change permutations
Coin Change Combinations: Ways to Make 5 with [1, 2, 5] The Permutation Trap (Ordered) • Treats [2,1,2], [1,2,2], [2,2,1] as 3 distinct ways • Leads to combinatorial explosion & redundancy Goal: Coins have no order; handful is unique! Canonical Loop Architecture for coin in coins: for x in range(coin, amount + 1): dp[x] += dp[x - coin] Step-by-Step DP Table Trace (Target Amount = 5) Index x: 0 1 2 3 4 5 Init: 1 0 0 0 0 0 dp[0]=1 (base) coin=1: 1 1 1 1 1 1 All 1s (only 1s) coin=2: 1 1 2 2 3 3 Adds coin 2 ways coin=5: 1 1 2 2 3 4 dp[5] = 4 ways! The 4 Unique Combinations for 5 1. [5] — single coin 2. [2, 2, 1] — two 2s and one 1 3. [2, 1, 1, 1] — one 2 and three 1s 4. [1, 1, 1, 1, 1] — five 1s Strict ascending order prevents duplicates ([1,2,2] is avoided; only [2,2,1] is counted) Key takeaway: Outer loop coin restriction forces canonical representation → O(amount × coins) time, O(amount) space.
Ways to make 5 with [1, 2, 5] overview diagram
Why

Why Order Doesn't Matter When Making Change

Phase 1: The Combinatorial Trap

Imagine you are building a cash register or automated vending system that needs to dispense change. You have coins of denominations and you need to make an exact target amount of 5. How many distinct ways can you form this total?
If you simply start listing every sequence of coin choices that adds up to 5, you will quickly run into a trap. For instance, is choosing a 2-cent coin followed by a 1-cent coin and another 2-cent coin different from choosing two 1-cent coins and then a 2-cent coin? If you treat them as separate events, you are counting permutations (ordered sequences).
Permutations treat , , and as three distinct transactions. But in currency, a handful of coins has no intrinsic order; holding two 2-cent coins and one 1-cent coin is a single unique physical combination. Without a strategy that enforces order-independence, your solution space explodes with redundant paths, making it impossible to scale to larger amounts.
Why Order Doesn't Matter When Making Change (Target = 5, Coins: [1, 2, 5]) Trap: Counting Permutations (Order Counts) Redundant sequences explode the solution space Group A: Coins {1, 2, 2} 2 1 2 [2, 1, 2] Also: [1,2,2] & [2,2,1] Group B: All Ones {1,1,1,1,1} Only 1 permutation: [1, 1, 1, 1, 1] Group C: Single Coin {5} Only 1 permutation: [5] Result: 9 Total Permutations Overcounts physical handfuls due to sequence! SORT Solution: Unique Combinations (Sorted) Enforce non-decreasing coin order to avoid duplicates 1. Single Coin (5) 5 Canonical: [5] 2. Mixed Coins (2 + 2 + 1) 2 2 1 Canonical: [1, 2, 2] 3. All Ones (1 + 1 + 1 + 1 + 1) 1 1 1 1 Canonical: [1, 1, 1, 1, 1] Result: Exactly 3 Unique Ways Each physical handful is counted precisely once!
Why Order Doesn't Matter When Making Change diagram
Model

The Nested-Loop Architecture for Unordered Coin Combinations

Phase 2: The Canonical Loop Ordering Model

To count combinations for making 5 with coins = without double-counting permutations like and , we must restrict how coins are introduced. Imagine a single-row array dp of size 6, where index stores the number of ways to form amount . We initialize dp[0] = 1 because there is exactly one way to make 0 (by picking no coins), and every other index starts at 0.
The secret to ignoring order lies in the loop architecture. Instead of iterating amounts in the outer loop and coins in the inner loop (which generates ordered permutations), we iterate through each coin one by one in the outer loop, and sweep through amounts from coin up to amount in the inner loop.
python
dp = [1, 0, 0, 0, 0, 0]  # dp[0] to dp[5]
coins = [1, 2, 5]

for coin in coins:
    for x in range(coin, amount + 1):
        dp[x] += dp[x - coin]
By locking the coin loop to the outside, we force the algorithm to consider all ways to form amounts using only the first coin (1), then update the table to include the second coin (2), and finally the third coin (5). This enforces a strictly ascending order of coin inclusion, making every generated combination unique.
python
dp = [1, 0, 0, 0, 0, 0]
coins = [1, 2, 5]
# Predict how dp looks after processing coin = 1
Nested-Loop Architecture for Unordered Coin Combinations (Target = 5) Outer loop coin inclusion prevents duplicate permutations like {2,1,2} vs {1,2,2} 1. The Canonical Loop Order coins = [1, 2, 5] | Target = 5 for coin in coins: for x in range(coin, amount + 1): dp[x] += dp[x - coin] 2. Why Order Doesn't Matter • Coin 1 runs first: builds base ways using only [1] • Coin 2 runs second: overlays pairs using [1, 2] • Coin 5 runs last: overlays [5] additions Ascending coin introduction locks sequence: {2, 1, 2} is impossible because coin 1 finishes before coin 2! 3. DP Table Evolution (Target Amount 0 to 5) Indices represent target amounts. Values count unique combinations. Amt 0 Amt 1 Amt 2 Amt 3 Amt 4 Amt 5 Init: 1 0 0 0 0 0 coin=1: 1 1 1 1 1 1 coin=2: 1 1 2 2 3 3 coin=5: 1 1 2 2 3 4 Result: dp[5] = 4 unique combinations ({5}, {2,2,1}, {2,1,1,1,1}, {1,1,1,1,1})
The Nested-Loop Architecture for Unordered Coin Combinations diagram
Worked example

Tracing the DP Table Step by Step for [1, 2, 5]

Phase 3: Worked example

To see the nested-loop architecture in action, let us trace the DP array for our locked example where coins = [1, 2, 5] and amount = 5. We initialize an array of size 6 (indices 0 to 5) with zeros, except for our base case: dp[0] = 1. This base case signifies that there is exactly 1 way to make an amount of 0 (by using no coins at all).

Step 1: Processing coin 1

When we process coin = 1, our outer loop picks the coin, and our inner loop updates every amount from 1 to 5 using the recurrence relation .
- For :
- For :
- For :
- For :
- For :
After processing coin 1, our array is [1, 1, 1, 1, 1, 1]. Every amount from 0 to 5 has exactly 1 way to be formed (using only 1-cent coins).

Step 2: Processing coin 2

Next, our outer loop moves to coin = 2. The inner loop now runs from 2 to 5, adding to .
- For : (representing combinations: and )
- For : (combinations: and )
- For : (combinations: , , and )
- For : (combinations: , , and )
After processing coin 2, our array updates to [1, 1, 2, 2, 3, 3].

Step 3: Processing coin 5

Finally, our outer loop selects coin = 5. The inner loop runs only for .
- For : (adding the single coin to our existing combinations)

Result

The final DP array after all coins have been processed is [1, 1, 2, 2, 3, 4]. Looking at the final index, dp[5] = 4. These 4 valid, unordered combinations matching our expected result are , , , and .
python
def change(amount: int, coins: list[int]) -> int:
    dp = [1] + [0] * amount
    for coin in coins:
        for x in range(coin, amount + 1):
            dp[x] += dp[x - coin]
    return dp[amount]
Tracing DP Table for coins = [1, 2, 5], Amount = 5 dp[x] += dp[x - coin] — Step-by-step evolution Initial Base Case dp[0] = 1, rest = 0 dp = 1 [0] 0 [1] 0 [2] 0 [3] 0 [4] 0 [5] Step 1: coin = 1 Updates all indices x from 1 to 5: dp[x] += dp[x - 1] 1 1 1 1 1 1 Step 2: coin = 2 Runs for x from 2 to 5: dp[x] += dp[x - 2] 1 1 2 2 3 3 Step 3 & Result: coin = 5 Runs only for x = 5: dp[5] += dp[0] 1 1 2 2 3 4 Final answer: dp[5] = 4 ways ([5], [2,2,1], [2,1,1,1], [1,1,1,1,1])
Tracing the DP Table Step by Step for [1, 2, 5] diagram
Practice

Predicting the DP Table for a Modified Coin Set

Phase 4: Practice

Now that you have traced the full progression for amount = 5 with coins = [1, 2, 5], let us test your mental model on a constrained variant of the same problem. Suppose we keep the exact same coin set coins = [1, 2, 5], but reduce our target amount to 4.
Recall our canonical state transition: keeping the outer loop over coins ensures each coin is processed in a fixed sequence, preventing permutations like and from being counted separately. When you evaluate coins = [1, 2, 5] for an amount = 4, every intermediate cell in your dp array must reflect only unique combinations of those coins summing to that partial amount.

The Challenge Task

What is the complete state of the dp array of size 4 (indices 0 through 4) after processing all coins, and what final value represents the total number of combinations to make amount = 4?
Work through the outer loop for coin 1, then coin 2, and finally coin 5, updating your array in place just as we did in the previous worked example. Keep strict track of how the inner loop bounds (x = coin to amount) prevent counting duplicate arrangements.
python
coins = [1, 2, 5]
amount = 4
dp = [1] + [0] * amount

# Trace the nested loops yourself:
# for coin in coins:
#     for x in range(coin, amount + 1):
#         dp[x] += dp[x - coin]

print(dp)
Apply

Transfer: Scaling the Unordered Coin Pattern to New Constraints

Phase 5: Scaling the Pattern

You have seen how the canonical coin-outer loop prevents duplicate permutations when making amount 5 with coins . The power of this dynamic programming model lies in its invariance to scaling. When constraints shift—such as introducing quantity limits, alternate target amounts, or currency denominations with different GCD properties—the core principle remains unchanged: enforce a fixed processing order of available resources before accumulating target states.
Consider how you would adapt this technique if each coin could be used at most twice, or if you needed to find combinations for a larger target like amount 12. The outer-coin architecture ensures that you never revisit an earlier coin once its transitions for all valid amounts have been calculated. This guarantees time complexity while maintaining exact uniqueness.
python
# Generalizing the canonical combination template
def count_combinations(coins, amount):
    dp = [0] * (amount + 1)
    dp[0] = 1
    for coin in coins:
        for x in range(coin, amount + 1):
            dp[x] += dp[x - coin]
    return dp[amount]
When faced with a new variation, your first diagnostic step should be checking whether the problem asks for combinations or permutations. If order still does not count, keep the outer loop anchored to the coin universe and let the inner loop sweep the target interval.
python
def count_combinations_modified(coins, amount):
    # Apply the canonical outer-coin loop to solve a modified variant
    pass

FAQ

How many ways can you make 5 using the coin set [1, 2, 5] when order does not matter?
There are 4 combinations: [5], [2, 2, 1], [2, 1, 1, 1], and [1, 1, 1, 1, 1]. Permutations like [1, 4] or [2, 1, 2] are treated as identical because order is ignored.
Why does looping coins on the outside prevent duplicate permutations?
Iterating through coins in the outer loop forces the algorithm to consider coins in a strict, ascending sequence. This ensures that once coin i is processed, we never look back at coin i-1, naturally eliminating duplicate orderings like [2, 1] after [1, 2].
What is the time and space complexity of the unordered coin change DP solution?
The time complexity is O(n * amount), where n is the number of coins and amount is the target value. The space complexity is O(amount) since we only need a 1D DP array to track combination counts.
What is the main pitfall when transitioning from permutation coin change to combination coin change?
The most common mistake is nesting the coin loop inside the amount loop, which calculates permutations (order matters) instead of combinations. To fix this, swap the loops so the coin loop is on the outside.

Keep learning