Description
Find distinct combinations of positive candidate values summing to target. Each input occurrence may be used once; candidates can repeat. Combination order does not matter.
Solution
def combination_sum2(candidates, target):
values = sorted(candidates)
result, path = [], []
def visit(start, remaining):
if remaining == 0:
result.append(path.copy())
return
for i in range(start, len(values)):
if i > start and values[i] == values[i - 1]:
continue
if values[i] > remaining:
break
path.append(values[i])
visit(i + 1, remaining - values[i])
path.pop()
visit(0, target)
return resultExamples
Example 1
- Input
[[10,1,2,7,6,1,5],8]- Output
[[1,1,6],[1,2,5],[1,7],[2,6]]
Four unique combinations reach 8.
Example 2
- Input
[[2,5,2,1,2],5]- Output
[[1,2,2],[5]]
Duplicate candidate positions do not duplicate answers.
Example 3
- Input
[[3],2]- Output
[]
No candidate can reach the target.
Approach
Sort the values and backtrack from a start index. Skip equal candidates at the same depth, stop once a candidate exceeds the remaining sum, and recurse from the next index to prevent reuse.
Time & space
O(n 2^n) worst-case time and O(n) auxiliary space excluding output, where n is the candidate count.