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
29 lines (24 loc) · 890 Bytes
/
combination-sum.py
File metadata and controls
29 lines (24 loc) · 890 Bytes
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
"""
Time: O(N^K), assuming the number of element in the combination that sums up to "target" is K.
For each element, there is N choices.
Which means the number of combination is N*N*N... for K times.
~= O(N^K)
Space: O(K)
K is approximate to target/min(candidates).
"""
class Solution:
def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
def helper(i, currSum, target):
if currSum>target:
return
if currSum==target:
ans.append(combination.copy())
return
for j in range(i, len(candidates)):
combination.append(candidates[j])
helper(j, currSum+candidates[j], target)
combination.pop()
ans = []
combination = []
helper(0, 0, target)
return ans