LeetCode 40 · Backtracking · concept: backtracking
Problem
Given candidates (which may contain duplicates) and a target, return all unique combinations summing to target. Each number is used at most once.
candidates = [10,1,2,7,6,1,5], target = 8 -> [[1,1,6],[1,2,5],[1,7],[2,6]]
Approach — sort + advance index + skip duplicate siblings
Combines two ideas already seen: use each element once by recursing on i+1 (not i, as in Combination Sum), and avoid duplicate combinations by sorting and skipping equal siblings (as in Subsets II).
def combinationSum2(candidates, target):
candidates.sort()
res = []
path = []
def backtrack(start, remaining):
if remaining == 0:
res.append(path[:])
return
for i in range(start, len(candidates)):
if i > start and candidates[i] == candidates[i - 1]:
continue # skip duplicate at this level
if candidates[i] > remaining:
break # sorted -> all later are too big
path.append(candidates[i])
backtrack(i + 1, remaining - candidates[i]) # i+1 -> each used once
path.pop()
backtrack(0, target)
return resTime O(2ⁿ) worst case, space O(n).
The two mechanics working together
i + 1in the recursive call → each element consumed at most once (vs. Combination Sum’s reuse via samei).i > startskip → no duplicate combinations from equal input values.breakoncandidates[i] > remaining→ sorting lets you abandon the rest of the loop early.
Key insight
“Each element once + duplicate inputs” = advance the index (i+1) and skip equal siblings (i > start), after sorting. It’s the synthesis of the two prior backtracking refinements; recognizing which combination of guards a problem needs is the skill.
Related
- concept: backtracking
- combines: Combination Sum + Subsets II
- prev: Subsets II · next: Word Search
Software engineering
Infrastructure & security
Computer science
Hardware & engineering