Combination Sum: Reuse Choice Backtracking Pattern

Learning Outcome

After this lesson, you should be able to prevent duplicate combinations by keeping a start index.

Problem Statement

Given distinct candidate numbers and a target, return all unique combinations where chosen numbers sum to target. A candidate may be reused.

Brute Force Approach

Try every ordered sequence. This creates duplicates like [2,3,2] and [3,2,2].

Optimized Approach

Backtrack with a start index. Reuse the same index when a candidate can be picked again, and move forward to avoid reordered duplicates.

Exact Pseudocode

answer = []
path = []
dfs(start, remaining):
  if remaining == 0:
    answer.add(copy(path))
    return
  for i from start to n - 1:
    if candidates[i] <= remaining:
      path.add(candidates[i])
      dfs(i, remaining - candidates[i])
      path.removeLast()
dfs(0, target)
return answer
  

Reference Code

class Solution:
    def combinationSum(self, candidates, target):
        answer = []
        path = []

        def dfs(start, remaining):
            if remaining == 0:
                answer.append(path[:])
                return

            for i in range(start, len(candidates)):
                if candidates[i] <= remaining:
                    path.append(candidates[i])
                    dfs(i, remaining - candidates[i])
                    path.pop()

        dfs(0, target)
        return answer
  

Sample Dry Run

Complexity

Edge Cases

• Candidates can be reused.
• Combinations should be unique by value order.
• remaining below 0 should be avoided or pruned.

Interview Checklist

• Use start index to prevent reordered duplicates.
• Call dfs(i, ...) to allow reuse.
• Copy the path when remaining reaches 0.

FAQs

Using i allows the same candidate to be reused.

The start index keeps combinations in nondecreasing candidate order.

Backtracking with reusable choices.