# 377. Combination Sum IV

Given an integer array with all positive numbers and no duplicates, find the number of possible combinations that add up to a positive integer target.

Example:

nums = [1, 2, 3]
target = 4
The possible combination ways are:
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)
Note that different sequences are counted as different combinations.
Therefore the output is 7.

# Solution

Approach 1: memoized recursion (top down).

Approach 2: DP (bottom up).

# Code (Python)

Approach 1:

    def combinationSum4(self, nums: List[int], target: int) -> int:
        if not nums:
            return 0 if target > 0 else 1
        nums.sort()
        # 1. memoized recursion
        #return self._combine(nums, target, {})
             
        @functools.lru_cache(None)
        def num_combinations(target):
            if target == 0:
                return 1
            if target < 0 or nums[0] > target:
                return 0
            result = 0
            for num in nums:
                if num <= target:
                    result += num_combinations(target - num)
            return result
        # 2. memoized recursion using python's built in cache
        #return num_combinations(target)
    
    def _combine(self, nums, target, memo):
        if target in memo:
            return memo[target]

        if target == 0:
            memo[target] = 1
        elif target < 0 or nums[0] > target:
            memo[target] = 0
        else:
            memo[target] = 0
            for num in nums:
                if num <= target:
                    memo[target] += self._combine(nums, target - num, memo)
        
        return memo[target]

Approach 2:

    def combinationSum4(self, nums: List[int], target: int) -> int:
        # DP
        count = [1] + [0] * target
        for total in range(1, len(count)):
            for num in nums:
                if num <= total:
                    count[total] += count[total-num]
        return count[-1]

# Code (C++)

Approach 1:

Approach 2: