Introduction

This problem is usually asking for all combinations of positive integers whose sum equals a target. The key choice is whether order matters. In most versions, 1 + 4 and 4 + 1 should count as the same combination, so the algorithm must avoid generating duplicate orderings.

Backtracking with a nondecreasing sequence

A clean solution is to build combinations in nondecreasing order. That way, once you choose a number, recursive calls may reuse it or choose larger numbers, but never smaller ones.

1def all_sums(target, start=1):
2    if target == 0:
3        return [[]]
4
5    results = []
6    for value in range(start, target + 1):
7        for suffix in all_sums(target - value, value):
8            results.append([value] + suffix)
9    return results
10
11
12print(all_sums(5))

Output:

1[[1, 1, 1, 1, 1],
2 [1, 1, 1, 2],
3 [1, 1, 3],
4 [1, 2, 2],
5 [1, 4],
6 [2, 3],
7 [5]]

Because the recursion never goes backward, 2 + 3 appears once and 3 + 2 never appears as a duplicate. That ordering discipline is the difference between solving the combination problem correctly and accidentally enumerating permutations.

Why the start parameter matters

The start argument is what prevents duplicate orderings. After choosing 2, the next recursive call only considers 2 and larger values. That means the search tree represents combinations, not permutations.

Without start, you would generate many duplicates and then need extra work to remove them.

Adding restrictions

The same backtracking structure can handle additional rules.

For example, if each number may be used at most once:

1def all_sums_no_reuse(target, values, index=0):
2    if target == 0:
3        return [[]]
4    if target < 0 or index >= len(values):
5        return []
6
7    results = []
8
9    for suffix in all_sums_no_reuse(target - values[index], values, index + 1):
10        results.append([values[index]] + suffix)
11
12    results.extend(all_sums_no_reuse(target, values, index + 1))
13    return results
14
15
16print(all_sums_no_reuse(5, [1, 2, 3, 4, 5]))

That version solves a different problem, but the recursion pattern is closely related.

When dynamic programming helps

If you only need the count of combinations, dynamic programming is often more efficient than generating every list. But if the task explicitly wants all possible sums, you eventually have to materialize the actual combinations, so output size becomes the dominant cost.

That is why backtracking is still a natural fit: it mirrors the structure of the answers being produced. It also makes it easy to add domain rules such as maximum part size, limited reuse, or restricted candidate values without changing the core search idea.

One more practical advantage of this recursive structure is that you can stream results as they are found instead of computing every combination up front. That can be useful when the caller wants to inspect combinations lazily or stop early after the first few valid solutions.

Common Pitfalls

The biggest mistake is not deciding whether order matters. If the problem wants combinations, generating permutations such as [1, 4] and [4, 1] is wrong.

Another common issue is forgetting the base case target == 0. That base case represents one valid completed combination and is what allows the recursion to build results upward.

Be careful with performance expectations too. The number of valid sums grows quickly, so generating all of them can become expensive for larger targets.

Finally, if zeros or negative numbers are allowed, the problem changes substantially. The simple positive-integer backtracking solution assumes every recursive step moves the sum closer to zero.

Summary

• Start by deciding whether the problem wants combinations or permutations.
• A nondecreasing backtracking search avoids duplicate orderings.
• The start parameter is what enforces combination-style generation.
• Dynamic programming is great for counts, but actual combination generation still needs output construction.
• Positive-integer assumptions keep the recursion finite and well-behaved.