1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
| class Solution:
def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
result,path = [],[]
sum_ = 0
used_list = [False for _ in candidates]
candidates.sort()
def combinationSum2_inner(candidates,target,sum_,start_index) ->List[List[int]]:
if sum_ > target: return
if sum_ == target:
result.append(path.copy())
return
for i in range(start_index,len(candidates)):
if sum_ > target: break
if i > 0 and candidates[i]==candidates[i-1] and used_list[i-1]==0:
continue
path.append(candidates[i])
sum_ += candidates[i]
used_list[i] = True
combinationSum2_inner(candidates,target,sum_,i+1)
reduce = path.pop()
sum_ -= reduce
used_list[i] = False
return result
return combinationSum2_inner(candidates,target,sum_,0)
|