forked from wuduhren/leetcode-python
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathcombination-sum.py
More file actions
executable file
·143 lines (119 loc) · 4.15 KB
/
combination-sum.py
File metadata and controls
executable file
·143 lines (119 loc) · 4.15 KB
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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
"""
the `helper()` check if the `target_remain` is 0.
If true, it means that the sum of `combination` is equal to the `target`. Put the `combination` to the `answer`.
If not, we For-loop each number, put it in the `combination` and try the `combination`. See if the number can make `target_remain` 0.
The `start` means the `candidates[start:]` are the candidate we only need to concider.
For example if
```
candidates = [2,3,6,7], target = 7
```
If we pick 3, we are not allow to pick 2 any more, or we will have duplicate combination.
We are only allow to pick the number at the same index or afterwards.
So in the For-loop, if the smallest candidate is larger than the `target_remain`, we don't need to check afterwards.
And that is why we need to sort the `candidates` in the first place.
```
candidates = [2,3,6,7]
target = 7
helper([], 0, 7)
helper([2], 0, 5)
helper([2, 2], 0, 3)
helper([2, 2, 2], 0, 1)
BREAK. When we are about to call helper([2, 2, 2, 2], 0, 1), we found that 2>target_remain.
helper([2, 2, 3], 1, 0) --> bingo
helper([2, 3], 1, 2)
BREAK. When we are about to call helper([2, 6], 2, 2), we found that 6>target_remain.
helper([3], 1, 4)
.
.
.
helper([6], 2, 1)
.
.
.
helper([7], 3, 0) --> bingo
```
"""
class Solution(object):
def combinationSum(self, candidates, target):
def helper(combination, start, target_remain):
if target_remain==0:
answer.append(combination)
for i in xrange(start, len(candidates)):
num = candidates[i] #try out if with num adding into combination can make target_remain 0
if num>target_remain: break
helper(combination+[num], i, target_remain-num)
candidates.sort()
answer = []
helper([], 0, target)
return answer
#Old Solution
class Solution(object):
def combinationSum(self, candidates, target):
def helper(candidates, target, combination):
if not candidates: return []
n = candidates[0]
if n>target:
return []
elif n==target:
return [combination+[n]]
else:
return helper(candidates, target-n, combination+[n]) + helper(candidates[1:], target, combination)
return helper(sorted(candidates), target, [])
# 2019/9/12 Update
class Solution(object):
def combinationSum(self, candidates, T):
answer = []
ans = []
first = 0
total = 0
candidates.sort()
memo = {}
for i, num in enumerate(candidates):
memo[num] = i
while True:
if total==T:
answer.append(ans[:])
if total>=T or first>=len(candidates):
if not ans: return answer
num = ans.pop()
first = memo[num]+1
total-=num
else:
ans.append(candidates[first])
total+=candidates[first]
# DFS
class Solution(object):
def combinationSum(self, candidates, T):
def dfs(index, target, path):
if target<0:
return
elif target==0:
opt.append(path)
else:
for i in xrange(index, len(candidates)):
num = candidates[i]
dfs(i, target-num, path+[num])
opt = []
candidates.sort()
dfs(0, T, [])
return opt
"""
Time: O(N^(T/M)), N is the number of candidates. T is target. M is min(candidates).
Space: O(T/M)
"""
class Solution(object):
def combinationSum(self, candidates, target):
def helper(remain, comb, start=0):
if remain==0:
ans.append(comb[:])
elif remain<0:
return
elif remain>0:
for i in xrange(start, len(candidates)):
candidate = candidates[i]
comb.append(candidate)
helper(remain-candidate, comb, i)
comb.pop()
ans = []
helper(target, [])
return ans