Algorithm

Combination Sum

Backtracking Pattern

Combination Sum

Given an array of distinct positive integers and a target, return every unique combination of the candidates that sums exactly to the target.

The same candidate may be used any number of times, so [2,2,3] is valid when 2 and 3 are both available. Two combinations are the same if they contain the same numbers with the same multiplicities regardless of order, so [2,2,3] and [2,3,2] count as one answer and only one may appear.

Return an empty list when no combination reaches the target exactly.

CONSTRAINTS
  • 1 <= candidates.length <= 30
  • 2 <= candidates[i] <= 40
  • 1 <= target <= 500
  • All candidates are distinct positive integers
  • Each candidate may be reused without limit
EXAMPLE 1
Input: candidates = [2,3,6,7], target = 7
Output: [[2,2,3],[7]]
2 + 2 + 3 = 7 reuses the candidate 2 twice, which is permitted. 7 alone also works. Note [3,2,2] does not appear separately — it is the same multiset as [2,2,3], and only one representative belongs in the output.
EXAMPLE 2
Input: candidates = [2,3,5], target = 8
Output: [[2,2,2,2],[2,3,3],[3,5]]
A single candidate may be repeated as many times as needed, so four 2s is a valid answer. Each combination is listed in non-decreasing order, which is how duplicates are avoided rather than filtered.
EXAMPLE 3
Input: candidates = [2], target = 1
Output: []
The smallest candidate already exceeds the target, so no sum can reach it. Every candidate is at least 2, so odd targets below the minimum are unreachable and an empty list is the correct answer.
EXAMPLE 4
Input: candidates = [7,3,2], target = 7
Output: [[7],[3,2,2]]
Same numbers as the first example minus 6, but supplied unsorted. The combinations are built in the order candidates appear, so [3,2,2] is non-decreasing with respect to the input's positions, not to the values — sorting first would give [2,2,3] instead. Either is accepted.
How many times may a single candidate be reused?
Without limit, bounded only by the target. That is the defining difference from Combinations, and in code it is a one-character change — passing i instead of i+1 to the recursive call.
Can the candidates contain duplicates or non-positive numbers?
Not here — all are distinct and at least 2. Both guarantees matter. Duplicate candidates would require an extra skip rule; a zero or negative candidate would make the search non-terminating, since the running total would stop decreasing.
Do [2,2,3] and [2,3,2] count as different answers?
No, they are the same combination and exactly one may appear. Suppressing the reorderings is what the start index accomplishes.
Would sorting the candidates first help?
It is not required for correctness, but it enables a stronger pruning rule: once a candidate exceeds the remaining amount, every later candidate does too, so the loop can break rather than continue. Worth mentioning even if you do not implement it.

Pick numbers that add up to target, and you may reuse a number freely. Same "no duplicate sets" issue as Combinations, so keep a start index — but allow the same number again by recursing with i (not i + 1). New power: track the amount remaining, and stop a branch the moment it goes negative.

The backtracking template

Every problem in this section is the same loop — three beats: choose, explore, un-choose.

python
def backtrack(state):
    if done(state):
        save(state)              # record the finished answer
        return
    for choice in choices(state):    # what can I pick right now?
        if not ok(choice):
            continue                 # prune: skip bad picks early
        apply(choice)                # CHOOSE
        backtrack(next_state)        # EXPLORE
        undo(choice)                 # UN-CHOOSE: put it back

Only four slots change between problems: done, choices, ok (pruning), and how you finish (save every answer, or return True at the first one). Fill those and the problem is solved.

What changes here
- A choice = pick candidate i from start..end (reuse allowed → recurse with i).
- Choices = candidates from start onward.
- Done = remaining hits 0 → save the path.
- Prune = remaining < 0 → stop (safe because all numbers are positive).
python
def combination_sum(candidates, target):
    res, path = [], []

    def backtrack(start, remain):
        if remain == 0:
            res.append(list(path))
            return
        if remain < 0:
            return                              # PRUNE: overshot
        for i in range(start, len(candidates)):
            path.append(candidates[i])          # CHOOSE
            backtrack(i, remain - candidates[i])# EXPLORE: 'i' allows reuse
            path.pop()                          # UN-CHOOSE

    backtrack(0, target)
    return res

backtrack(i, ...) is the whole difference from Combinations — i keeps the current number available, i + 1 would forbid reuse. Overshoot pruning is valid only because every candidate is positive, so once you pass the target you can never come back.

Trace [2,3,6,7], target 7: 2+2+3 = 7 → [2,2,3]; 7 → [7]. Result [[2,2,3],[7]].

Interactive Strategy Visualization

The Backtracking Mindset

Think of this as exploring a maze. When you hit a dead end (target < 0), you step back and try a different path.

Available Choices
2
3
5
Target To Reach
5
Your Current Path
[ Empty ]
Start with an empty path and a target of 5.
The Choice Tree

Every time we pick a number, we create a new branch. We keep picking until we either hit the Target (Success) or Overshoot (Failure).

The 3-Step Pattern
1. Choose: Add number to path.
2. Explore: Call recursion.
3. Un-choose: Remove it to try others.
Smart Pruning

If our sum is already too big, any further numbers will only make it bigger. We "Prune" (cut) the branch early to save time.

Exponential Enumerate Then Filter By Sum
→
O(N^(T/M)) Backtracking With Overshoot Pruning
→
O(N^(T/M)) Sorted With Early Loop Break