This problem follows the Backtrack with Reuse pattern, commonly found in the Backtracking category. Recognizing this pattern is key to solving it efficiently in an interview setting.
Try each candidate. Recurse with same index (reuse allowed). Backtrack if sum exceeds target.
Passing 'i' (not 'i+1') allows reuse of the same element. Sorting + early termination when candidate > target is the key optimization.
result = []
candidates.sort()
def backtrack(start, target, current):
if target == 0:
result.append(current[:])
return
for i in range(start, len(candidates)):
if candidates[i] > target: break
current.append(candidates[i])
backtrack(i, target - candidates[i], current)
current.pop()
backtrack(0, target, [])
return resultPractice Combination Sum and similar Backtracking problems with flashcards. Build pattern recognition through active recall.
Practice this problem