# 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