-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathcombination-sum.py
More file actions
64 lines (55 loc) · 1.99 KB
/
combination-sum.py
File metadata and controls
64 lines (55 loc) · 1.99 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
# encoding: utf-8
__author__ = 'zhangwei'
# 递归版本
class Solution:
# @param {integer[]} candidates
# @param {integer} target
# @return {integer[][]}
def combinationSum(self, candidates, target):
candidates.sort() # 排序
ret, stack = [], []
self.aux(candidates, 0, ret, stack, target)
return ret
# auxiliary method
def aux(self, candidates, begin, ret, stack, target):
if target == 0:
ret.append(stack[::])
return
for i in xrange(begin, len(candidates)):
if candidates[i] <= target:
stack.append(candidates[i])
self.aux(candidates, i, ret, stack, target-candidates[i])
stack.pop()
# 迭代版本
class Solution:
# @param {integer[]} candidates
# @param {integer} target
# @return {integer[][]}
def combinationSum(self, candidates, target):
down, up = 1, 2 # 分别表示「下探」和「回溯」
candidates.sort() # 排序
stack = [0]
sums = 0
pre, dir = 0, down
ret = []
while len(stack) > 0:
cur = stack[-1]
if dir == down:
if sums == target:
ret.append([candidates[i] for i in stack[1:]])
stack.pop()
pre, dir, sums = cur, up, sums-candidates[cur]
elif sums + candidates[cur] <= target:
stack.append(cur)
pre, dir, sums = cur, down, sums+candidates[cur]
else:
stack.pop()
pre, dir, sums = cur, up, sums-candidates[cur]
else:
if pre < len(candidates)-1 and sums + candidates[pre+1] <= target:
stack.append(pre+1)
pre, dir, sums = cur, down, sums+candidates[pre+1]
else:
stack.pop()
pre, dir, sums = cur, up, sums-candidates[cur]
return ret