forked from wuduhren/leetcode-python
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathcombination-sum-iv.py
More file actions
executable file
·66 lines (48 loc) · 1.5 KB
/
combination-sum-iv.py
File metadata and controls
executable file
·66 lines (48 loc) · 1.5 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
class Solution(object):
def combinationSum4(self, nums, target):
def helper(t):
if t<0: return 0
if dp[t]>=0: return dp[t]
ans = 0
for num in nums:
ans += helper(t-num)
dp[t] = ans
return ans
dp = [-1]*(target+1)
dp[0] = 1
for i in xrange(target+1):
helper(i)
return dp[target]
"""
Time: O(TN), T is the value of target and N is the count of nums.
Space: O(T)
"""
"""
dp[n] := number of combs sums up to n
For example, lets say target is 32 and nums is [4,2,1].
dp[32] = dp[28]+dp[30]+dp[31]
Since the combs of dp[28] adds 4 will all equals to 32.
Since the combs of dp[30] adds 2 will all equals to 32.
Since the combs of dp[31] adds 1 will all equals to 32.
...
dp[28] = dp[24]+dp[26]+dp[27]
Since the combs of dp[28] adds 4 will all equals to 24.
Since the combs of dp[28] adds 2 will all equals to 26.
Since the combs of dp[28] adds 1 will all equals to 27.
...
Time: O(TN), T is the value of target and N is the count of nums.
Space: O(T)
"""
class Solution(object):
def combinationSum4(self, nums, target):
dp = [0]*(target+1)
dp[0] = 1
t = 1
while t<=target:
combs = 0
for num in nums:
if t-num<0: continue
combs += dp[t-num]
dp[t] = combs
t += 1
return dp[target]