Combination Sum Backtracking DSA Solution

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.

Input	Output	Why
`candidates = [2,3,6,7], target = 7`	`[[2,2,3],[7]]`	2+2+3 and 7 both reach the target.

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

Step	State	Result
Start	remaining=7, path=[]	Try candidate 2
Reuse 2	path=[2,2], remaining=3	Still allowed because dfs uses i
Pick 3	path=[2,2,3], remaining=0	Copy answer
Try 7	path=[7], remaining=0	Copy answer

Complexity

Measure	Value	Reason
Time	O(number of valid states)	The search tree depends on target and candidate values.
Space	O(target / minCandidate)	The recursion path depth is bounded by repeated use of the smallest candidate.

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

Why call dfs with i instead of i + 1?

Using i allows the same candidate to be reused.

How are duplicates avoided?

The start index keeps combinations in nondecreasing candidate order.

What is the core pattern?

Backtracking with reusable choices.

Combination Sum: Reuse Choice Backtracking Pattern