forked from yingl/LintCodeInPython
-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathcombination_sum_ii.py
32 lines (30 loc) · 1.04 KB
/
combination_sum_ii.py
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
# -*- coding: utf-8 -*-
class Solution:
"""
@param candidates: Given the candidate numbers
@param target: Given the target number
@return: All the combinations that sum to target
"""
def combinationSum2(self, candidates, target):
# write your code here
self.ret = []
self.target = target
candidates.sort()
self._combinationSum2(candidates, [], 0, 0)
return self.ret
def _combinationSum2(self, candidates, comb, i, _sum):
if _sum == self.target:
self.ret.append(comb[:])
elif _sum > self.target:
return
else:
if i <= len(candidates):
prev = None
j = i
while j < len(candidates):
if candidates[j] != prev:
prev = candidates[j]
comb.append(candidates[j])
self._combinationSum2(candidates, comb, j + 1, _sum + prev)
comb.pop()
j += 1