# 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: