aboutsummaryrefslogtreecommitdiff
path: root/combination_sum4.py
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