-
Notifications
You must be signed in to change notification settings - Fork 0
/
combination_sum.py
46 lines (35 loc) · 1.25 KB
/
combination_sum.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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
class Solution(object):
def combinationSum(self, nums, target):
self.ans = 0
nums.sort()
def dfs(nums, ans, i, target, path=[]):
if target < 0:
return
if target == 0:
self.ans += 1
return
for x in range(i, len(nums)):
dfs(nums, self.ans, x, target-nums[x], path+[nums[x]])
dfs(nums, self.ans, 0, target)
return self.ans
def combinationSum_2(self, nums, target):
nums.sort()
ans = []
def dfs(idx, path, target):
if target < 0:
return
if target == 0:
ans.append(path)
# while idx > 0 and nums[idx-1] == nums[idx]:
# idx += 1
for i in range(idx, len(nums)):
if i > idx and nums[i] == nums[i-1]:
continue
if nums[i] > target:
return
dfs(i+1, path+[nums[i]], target-nums[i])
dfs(0, [], target)
return ans
abc = Solution()
# print (abc.combinationSum([2,3,6,7], 7))
print (abc.combinationSum_2([10,1,2,7,6,1,5] ,8))