Description
Find all combinations that sum to target, each number used once.
Constraints
- Time Complexity:
O(2^n) - Space Complexity:
O(n)
Tags
arraybacktracking
def combinationSum2(candidates, target):
candidates.sort()
res = []
def backtrack(cur, pos, target):
if target == 0:
res.append(cur.copy())
return
if target <= 0:
return
prev = -1
for i in range(pos, len(candidates)):
if candidates[i] == prev:
continue
cur.append(candidates[i])
backtrack(cur, i + 1, target - candidates[i])
cur.pop()
prev = candidates[i]
backtrack([], 0, target)
return res