Introduction

Finding all combinations of numbers that add up to a target is a classic backtracking problem. The exact solution depends on the rules: whether each number can be used once or many times, whether duplicates exist in the input, and whether order matters.

Clarify the problem rules first

Two similar-looking problems behave very differently:

• each input value may be used once
• values may be reused unlimited times

There is also a duplicate-handling question. If the list contains repeated values, you must decide whether combinations that differ only by choosing equivalent elements should be treated as the same result.

The most common interview-style version is:

• order does not matter
• each candidate may be used once or repeatedly, depending on the variant
• combinations should be unique

Backtracking for the reusable-values variant

If a number can be reused many times, the recursive step keeps the current index available.

1def combination_sum(candidates, target):
2    candidates = sorted(candidates)
3    result = []
4
5    def backtrack(start, remaining, path):
6        if remaining == 0:
7            result.append(path.copy())
8            return
9        if remaining < 0:
10            return
11
12        for i in range(start, len(candidates)):
13            value = candidates[i]
14            path.append(value)
15            backtrack(i, remaining - value, path)
16            path.pop()
17
18    backtrack(0, target, [])
19    return result
20
21
22print(combination_sum([2, 3, 6, 7], 7))

Output:

[[2, 2, 3], [7]]

The key detail is backtrack(i, ...) rather than backtrack(i + 1, ...), which allows reuse of the same candidate.

Backtracking for the use-each-number-once variant

If each number may be used at most once, move to the next index after choosing a value.

1def combination_sum_once(candidates, target):
2    candidates.sort()
3    result = []
4
5    def backtrack(start, remaining, path):
6        if remaining == 0:
7            result.append(path.copy())
8            return
9        if remaining < 0:
10            return
11
12        prev = None
13        for i in range(start, len(candidates)):
14            value = candidates[i]
15            if prev == value:
16                continue
17            if value > remaining:
18                break
19
20            path.append(value)
21            backtrack(i + 1, remaining - value, path)
22            path.pop()
23            prev = value
24
25    backtrack(0, target, [])
26    return result
27
28
29print(combination_sum_once([10, 1, 2, 7, 6, 1, 5], 8))

Here the prev check avoids duplicate combinations from repeated input values.

Why sorting matters

Sorting is not just cosmetic. It enables two useful optimizations:

• early stopping when value > remaining
• easy duplicate skipping

Without sorting, the backtracking tree becomes larger and duplicate handling becomes messier.

Counting solutions instead of listing them

If you only need the number of combinations rather than the combinations themselves, dynamic programming may be a better fit than full backtracking. But if the actual combinations must be returned, backtracking remains the clearest direct solution.

For example, counting ways to reach a target with unlimited reuse:

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

This is useful when the output itself would be too large to materialize.

Complexity considerations

There is no magic polynomial-time shortcut for listing all valid combinations, because the output itself can be exponentially large. The best you can usually do is prune aggressively and avoid duplicates.

Good pruning practices:

• sort candidates
• stop when remaining becomes negative
• stop early when the current value exceeds the remaining target
• skip duplicate candidates at the same recursion depth

These do not change the worst-case nature of the problem, but they often reduce work significantly on real inputs.

Common Pitfalls

The most common mistake is not deciding whether values can be reused, then writing recursion that solves the wrong problem. Another is failing to skip duplicates when the input contains repeated numbers, which produces duplicate combinations in the output. Developers also often forget to sort first, which makes pruning and uniqueness harder. Modifying and storing the same path list without copying it is another classic bug because all results end up referencing the same list object. Finally, some solutions generate permutations rather than combinations because they restart from index zero at every recursive step.

Summary

• Backtracking is the standard way to list all combinations matching a target sum.
• Use backtrack(i, ...) when numbers may be reused.
• Use backtrack(i + 1, ...) when each input value may be used once.
• Sort first so pruning and duplicate skipping become straightforward.
• Dynamic programming is useful when you only need counts, not the actual combinations.
• Define the rules clearly before coding, because small rule changes produce different algorithms.