blob: c4b0b05abd9e0ba275002946e07bc9042f0cf981 (
plain)
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
|
# 377. Combination Sum IV
"""
given an array of disticint integers 'nums' and a target integer 'target',
return the number of possible combinations that add up to 'target'. the test
cases are generated such that the answer can fit in a 32 bit integer.
"""
class Solution(object):
def combinationSum4(self, nums, target):
nums.sort()
memo = {}
def helper(n):
if n in memo:
return memo[n]
if n == 0:
return 1
if n < nums[0]:
return 0
cnt = 0
for i in nums:
if n - i < 0:
break
cnt += helper(n - i)
memo[n] = cnt
return cnt
return helper(target)
if __name__ == "__main__":
obj = Solution()
print(obj.combinationSum4([1, 2, 3], 4)) # expect: 7
print(obj.combinationSum4([9], 3)) # expect: 0
|