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.



Follow up:
What if negative numbers are allowed in the given array?
How does it change the problem?
What limitation we need to add to the question to allow negative numbers? 

Credits:Special thanks to @pbrother for adding this problem and creating all test cases.

Difficulty: interview

Starter code:

class Solution:
    def combinationSum4(self, nums: List[int], target: int) -> int:
        

Solutions:
class Solution:
     def combinationSum4(self, nums, target):
         """
         :type nums: List[int]
         :type target: int
         :rtype: int
         """
         cache = {}
         def f(val):
           if val == target:
             return 1
 
           total = 0
           remain = target - val
           for num in nums:
             if num <= remain:
               k = val+num
               if k in cache:
                 total += cache[k]
               else:
                 cache[k] = f(val + num)
                 total += cache[k]
           return total
         
         return f(0)

class Solution:
     def combinationSum4(self, nums, target):
         """
         :type nums: List[int]
         :type target: int
         :rtype: int
         """
         record={0:1}
         def helper(target):
             if target in record:
                 return record[target]
             res=0
             for x in nums:
                 if target>=x:
                     res+=helper(target-x)
             record[target]=res
             return res
         
         
         return helper(target)
 
         
         
 
 


class Solution(object):
     def combinationSum4(self, nums, target):
         """
         :type nums: List[int]
         :type target: int
         :rtype: int
         """
         dp = [0] + [-1] * target
 
         def calc(target):
             if target == 0:
                 return 1
             if dp[target] >= 0:
                 return dp[target]
             count = 0
             for n in nums:
                 if target - n >= 0:
                     tmp = calc(target - n)
                     if tmp >= 0:
                         count += tmp
             dp[target] = count
             return count
         ans = calc(target)
         print(ans)
         print(dp)
         return ans
 


class Solution:
     # recursive, time limit exceeded
     def combinationSum4_1(self, nums, target):
         """
         :type nums: List[int]
         :type target: int
         :rtype: int
         """
         res = 0
         if target == 0:
             return 1
         
         for i in range(len(nums)):
             if target >= nums[i]:
                 res += self.combinationSum4(nums, target - nums[i])
         return res
 
     # top down using memory
     def combinationSum4_2(self, nums, target):
         """
         :type nums: List[int]
         :type target: int
         :rtype: int
         """
         dp = [-1] * (target + 1)
         dp[0] = 1
         return self.helper(dp, nums, target)
     
     def helper(self, dp, nums, target):
         if dp[target] != -1:
             return dp[target]
         
         res = 0
         for i in range(len(nums)):
             if target >= nums[i]:
                 res += self.helper(dp, nums, target - nums[i])
         dp[target] = res
         return res
     
     # bottom up
     def combinationSum4(self, nums, target):
         """
         :type nums: List[int]
         :type target: int
         :rtype: int
         """
         dp = [0] * (target + 1)
         dp[0] = 1
         for i in range(target + 1):
             for num in sorted(nums):
                 if i < num: break
                 dp[i] += dp[i - num]
         return dp[-1]

class Solution:
     def combinationSum4(self, nums, target):
         """
         :type nums: List[int]
         :type target: int
         :rtype: int
         """
         
         dp = [0 for x in range(target+1)]
         dp[0] = 1
         for x in range(1, target+1):
             for elem in nums:
                 if x >= elem:
                     dp[x]+=dp[x - elem]
         return dp[-1]

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

class Solution:
     # recursive, time limit exceeded
     def combinationSum4_1(self, nums, target):
         """
         :type nums: List[int]
         :type target: int
         :rtype: int
         """
         res = 0
         if target == 0:
             return 1
         
         for i in range(len(nums)):
             if target >= nums[i]:
                 res += self.combinationSum4(nums, target - nums[i])
         return res
 
     # top down using memory
     def combinationSum4_2(self, nums, target):
         """
         :type nums: List[int]
         :type target: int
         :rtype: int
         """
         dp = [-1] * (target + 1)
         dp[0] = 1
         return self.helper(dp, nums, target)
     
     def helper(self, dp, nums, target):
         if dp[target] != -1:
             return dp[target]
         
         res = 0
         for i in range(len(nums)):
             if target >= nums[i]:
                 res += self.helper(dp, nums, target - nums[i])
         dp[target] = res
         return res
     
     # bottom up
     def combinationSum4(self, nums, target):
         """
         :type nums: List[int]
         :type target: int
         :rtype: int
         """
         dp = [0] * (target + 1)
         dp[0] = 1
         for i in range(target + 1):
             for num in sorted(nums):
                 if i < num: break
                 dp[i] += dp[i - num]
         return dp[-1]

class Solution:
     # recursive, time limit exceeded
     def combinationSum4_1(self, nums, target):
         """
         :type nums: List[int]
         :type target: int
         :rtype: int
         """
         res = 0
         if target == 0:
             return 1
         
         for i in range(len(nums)):
             if target >= nums[i]:
                 res += self.combinationSum4(nums, target - nums[i])
         return res
 
     # top down using memory
     def combinationSum4_2(self, nums, target):
         """
         :type nums: List[int]
         :type target: int
         :rtype: int
         """
         dp = [-1] * (target + 1)
         dp[0] = 1
         return self.helper(dp, nums, target)
     
     def helper(self, dp, nums, target):
         if dp[target] != -1:
             return dp[target]
         
         res = 0
         for i in range(len(nums)):
             if target >= nums[i]:
                 res += self.helper(dp, nums, target - nums[i])
         dp[target] = res
         return res
     
     # bottom up
     def combinationSum4(self, nums, target):
         """
         :type nums: List[int]
         :type target: int
         :rtype: int
         """
         dp = [0] * (target + 1)
         dp[0] = 1
         for i in range(target + 1):
             for j in range(len(nums)):
                 if i - nums[j] >= 0:
                     dp[i] += dp[i - nums[j]]
         return dp[-1]

class Solution:
     def combinationSum4(self, nums, target):
         """
         :type nums: List[int]
         :type target: int
         :rtype: int
         """
         def dfs(nums,target,memo):  
             if target in memo:
                 return memo[target]
             
             if target < 0:
                 return
             if target == 0:
                 memo[target] = 1
                 return
             
             memo[target] = 0
             for num in nums:
                 dfs(nums, target-num,memo)
                 if target-num >= 0:
                     memo[target] += memo[target-num] 
                 
         dfs.count = 0
         nums.sort()
         memo = {}
         dfs(nums,target,memo)
         
         return memo[target]
         


class Solution:
     def combinationSum4(self, nums, target):
         """
         :type nums: List[int]
         :type target: int
         :rtype: int
         """
         self.dp = [-1]*(target+1)
         self.dp[0] = 1
         return self.cSUtil(nums, target)
         
         
     def cSUtil(self, nums, target):
         if target < 0:
             return 0
         if self.dp[target] != -1:
             return self.dp[target]
         res = 0
         for num in nums:
             target -= num
             res += self.cSUtil(nums, target)
             target += num
         self.dp[target] = res
         return res

class Solution:
     def combinationSum4(self, nums, target):
         """
         :type nums: List[int]
         :type target: int
         :rtype: int
         """
         return self.use_dp(nums, target)
     
     def use_dfs(self, nums, target):
         self.result = 0
         nums.sort()
         self.dfs(nums, target)
         return self.result
     
     def dfs(self, nums, target):
         if target == 0:
             self.result += 1
             return
         
         for num in nums:
             if num > target:
                 break
             self.dfs(nums, target - num)
             
     def use_recursion_dp(self, nums, target):
         dp = [-1] * (target + 1)
         dp[0] = 1
         nums.sort()
         return self.dp_dfs(nums, target, dp)
     
     def dp_dfs(self, nums, target, dp):
         if dp[target] != -1:
             return dp[target]
         result = 0
         for num in nums:
             if num > target:
                 break
             result += self.dp_dfs(nums, target - num, dp)
         dp[target] = result
         return result
     
     def use_dp(self, nums, target):
         dp = [0] * (target + 1)
         dp[0] = 1
         for item in range(1, len(dp)):
             for num in nums:
                 if item - num >= 0:
                     dp[item] += dp[item - num]
         return dp[target]


class Solution:
     def combinationSum4(self, nums, target):
         """
         :type nums: List[int]
         :type target: int
         :rtype: int
         """
         if not nums:
             return 0
         n_nums = len(nums)
         # combinations = [[0]*(n_nums+1)]*(target+max(nums)+3)
         combinations = [[0]*(n_nums+1) for i in range(target+max(nums)+3)]
         for i in range(1, target + 1):
             cur_sum = 0
             for j in range(n_nums):
                 if i == nums[j]:
                     combinations[i][j] = 1
                 else:
                     combinations[i][j] = combinations[i - nums[j]][n_nums]
                 cur_sum += combinations[i][j]
             combinations[i][n_nums]= cur_sum
         return combinations[target][n_nums]
             
         


class Solution:
     count = 0
     def combinationSum4(self, nums, target):
         """
         :type nums: List[int]
         :type target: int
         :rtype: int
         """
         comb =  [0]*(target + 1)
         comb[0] = 1
         for i in range(1, len(comb)):
             for j in range(0, len(nums)):
                 if i - nums[j] >= 0:
                     comb[i] += comb[i - nums[j]]    
         return comb[target]
     
 #         self.helper(nums, 0, target, 0)
 #         return self.count
     
 #     def helper(self, nums, i, target, Sum):
 #         if i >= len(nums) or Sum > target:
 #             return 
 #         if Sum == target:
 #             self.count += 1
 #             return
         
 #         for j in range(0, len(nums)):
 #             self.helper(nums, j, target, Sum + nums[j])