Introduction

The coin change problem has two similar-looking versions that developers often mix up: combinations and permutations. Combinations ignore order, while permutations treat different orderings as distinct results. If the task is to list every ordered way to reach a target sum, you need a backtracking approach that explores all choices at each remaining total.

Clarify the Problem First

For coins [1, 2] and target 3:

• combination results are [1,1,1] and [1,2]
• permutation results are [1,1,1], [1,2], and [2,1]

That distinction changes both the algorithm and the output size. Permutations grow much faster because order matters.

Backtracking to List All Permutations

The most direct way to generate every ordered solution is recursion with a remaining sum and a current path.

1def find_permutations(coins, target):
2    results = []
3
4    def backtrack(remaining, path):
5        if remaining == 0:
6            results.append(path.copy())
7            return
8        if remaining < 0:
9            return
10
11        for coin in coins:
12            path.append(coin)
13            backtrack(remaining - coin, path)
14            path.pop()
15
16    backtrack(target, [])
17    return results
18
19
20coins = [1, 2, 3]
21target = 4
22print(find_permutations(coins, target))

This explores every valid ordering and stores each completed sequence.

Why This Finds Permutations

Notice that the loop always starts from the full coin list again. That means after choosing 2, the algorithm can still choose 1 next, which produces [2,1,...] separately from [1,2,...].

If you wanted combinations instead, you would carry a starting index and avoid revisiting earlier choices.

Avoiding Unnecessary Work

Sorting coins can make pruning easier, especially if you stop once a coin exceeds the remaining total.

1def find_permutations_sorted(coins, target):
2    coins = sorted(coins)
3    results = []
4
5    def backtrack(remaining, path):
6        if remaining == 0:
7            results.append(path.copy())
8            return
9
10        for coin in coins:
11            if coin > remaining:
12                break
13            path.append(coin)
14            backtrack(remaining - coin, path)
15            path.pop()
16
17    backtrack(target, [])
18    return results

This does not change correctness, but it reduces needless recursive calls.

Counting Without Listing

Sometimes you only need the number of permutations, not the actual lists. Then memoization is much cheaper.

1from functools import lru_cache
2
3def count_permutations(coins, target):
4    coins = tuple(coins)
5
6    @lru_cache(maxsize=None)
7    def solve(remaining):
8        if remaining == 0:
9            return 1
10        if remaining < 0:
11            return 0
12        return sum(solve(remaining - coin) for coin in coins)
13
14    return solve(target)
15
16print(count_permutations((1, 2, 3), 4))

This counts ordered solutions efficiently without building every path in memory.

Complexity Matters

Listing all permutations is inherently expensive because the output itself can be large. No algorithm can avoid that if you truly need every sequence.

That means you should ask early:

1. Do I need all sequences?
2. Or only the count?
3. Or only one valid sequence?

Choosing the wrong version leads to unnecessary runtime and memory use.

Handling Duplicate Coin Values

If the input coin list itself contains duplicates, such as [1, 1, 2], the naive algorithm can generate duplicate outputs. In most coin-change problems, denominations are unique by definition, so normalize first.

coins = sorted(set(coins))

This avoids duplicate branches caused by repeated equal denominations.

Practical Testing

Use small known examples:

print(find_permutations([1, 2], 3))
# expected ordered results: [1,1,1], [1,2], [2,1]

Small fixtures make it obvious whether your code is counting combinations or permutations by accident.

Common Pitfalls

• Confusing permutations with combinations and using the wrong recursion strategy.
• Trying to list all solutions when only the count is needed.
• Forgetting to stop recursion when remaining total becomes negative.
• Allowing duplicate coin values in the input and generating duplicate outputs.
• Underestimating output size and running out of memory for larger targets.

Summary

• For permutation-style coin change, order matters and [1,2] differs from [2,1].
• Backtracking is the clearest way to list every ordered solution.
• Memoization is better when you only need the count.
• Normalize coin denominations to avoid duplicate branches.
• Test with small examples to confirm you solved the right variant of the problem.