forked from shuboc/LeetCode-2
-
Notifications
You must be signed in to change notification settings - Fork 0
/
combination-sum.py
40 lines (37 loc) · 1.46 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
# Time: O(k * n^k)
# Space: O(k)
#
# Given a set of candidate numbers (C) and a target number (T),
# find all unique combinations in C where the candidate numbers sums to T.
#
# The same repeated number may be chosen from C unlimited number of times.
#
# Note:
# All numbers (including target) will be positive integers.
# Elements in a combination (a1, a2, ... , ak) must be in non-descending order. (ie, a1 <= a2 <= ... <= ak).
# The solution set must not contain duplicate combinations.
# For example, given candidate set 2,3,6,7 and target 7,
# A solution set is:
# [7]
# [2, 2, 3]
#
class Solution:
# @param candidates, a list of integers
# @param target, integer
# @return a list of lists of integers
def combinationSum(self, candidates, target):
result = []
self.combinationSumRecu(sorted(candidates), result, 0, [], target)
return result
def combinationSumRecu(self, candidates, result, start, intermediate, target):
if target == 0:
result.append(list(intermediate))
while start < len(candidates) and candidates[start] <= target:
intermediate.append(candidates[start])
self.combinationSumRecu(candidates, result, start, intermediate, target - candidates[start])
intermediate.pop()
start += 1
if __name__ == "__main__":
candidates, target = [2, 3, 6, 7], 7
result = Solution().combinationSum(candidates, target)
print result