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
27
28
29
30
31
32
33
34
35
36
37
|
# 40. Combination Sum II
"""
given a collection of candidate numbers and a target number, find all unique
combinations in 'candidates' where the candidate numbers sum to 'target'.
each number in 'candidates' may only be used once
"""
class Solution(object):
def dfs(self, candidates, target, idx, path, res):
if target <= 0:
if target == 0:
res.append(path)
return
for i in range(idx, len(candidates)):
if i > idx and candidates[i] == candidates[i - 1]:
continue
self.dfs(
candidates, target - candidates[i], i + 1, path + [candidates[i]], res
)
def combinationSum2(self, candidates, target):
"""
:type candidates: List[int]
:type target: int
:rtype: List[List[int]]
"""
ans = []
self.dfs(sorted(candidates), target, 0, [], ans)
return ans
if __name__ == "__main__":
obj = Solution()
print(obj.combinationSum2(candidates=[10, 1, 2, 7, 6, 1, 5], target=8))
print(obj.combinationSum2(candidates=[2, 5, 2, 1, 2], target=5))
|