-
Notifications
You must be signed in to change notification settings - Fork 0
/
combination_sum.py
63 lines (53 loc) · 1.61 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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
import json
class Solution(object):
def __init__(self):
self.candidates = []
self.results = []
def search(self, state, target):
if target == 0:
result = [i for i in state]
self.results.append(result)
# print(result)
return
for candidate in self.candidates:
if len(state) == 0 or candidate >= state[-1]: # important condition
if target-candidate >= 0:
state.append(candidate)
self.search(state, target-candidate)
state.pop()
return
def combinationSum(self, candidates, target):
"""
:type candidates: List[int]
:type target: int
:rtype: List[List[int]]
"""
self.candidates = candidates
self.results = []
self.search([], target)
return self.results
def stringToIntegerList(input):
return json.loads(input)
def stringToInt(input):
return int(input)
def int2dArrayToString(input):
return json.dumps(input)
def main():
import sys
def readlines():
for line in sys.stdin:
yield line.strip('\n')
lines = readlines()
while True:
try:
line = lines.next()
candidates = stringToIntegerList(line)
line = lines.next()
target = stringToInt(line)
ret = Solution().combinationSum(candidates, target)
out = int2dArrayToString(ret)
print out
except StopIteration:
break
if __name__ == '__main__':
main()