[LeetCode] 377. Combination Sum IV

 Problem : https://leetcode.com/problems/combination-sum-iv/

This quiz is similar to "Coin Change". 

Assume taking nums[i], find the combination for sum = target - nums[i].

Time complexity = O ( M * N ). M = target, N = len(nums)

Top-down solution:

class Solution:
    def combinationSum4(self, nums: List[int], target: int) -> int:
        N = len(nums)
        nums.sort()
        
        @lru_cache(maxsize = None)
        def helper(remain):
            if remain == 0: return 1
            
            result = 0
            
            for i in range(N):
                if nums[i] <= remain:
                    result += helper(remain - nums[i])
                else:
                    break
            
            return result

        return helper(target)

Bottom-up solution:

class Solution:
    def combinationSum4(self, nums: List[int], target: int) -> int:
        dp = [0] * (target + 1)
        dp[0] = 1
        
        nums.sort()
        
        for combo in range(1, target+1):
            for n in nums:
                if n > combo:
                    break
                    
                dp[combo] += dp[combo - n]
        
        return dp[target]

Follow-up question:

To allow negative number in the given array, we need to limit the ouput combination length. Otherwise, it won't be able to stop the searching.