Combination Sum Iv
Created: March 8, 2020 by [lek-tin]
Last updated: March 8, 2020
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?
Solution (DFS with memoization)
class Solution:
def combinationSum4(self, nums: List[int], target: int) -> int:
nums.sort()
memo = {}
result = self.dfs(nums, target, memo)
return result
def dfs(self, nums, target, memo):
if target in memo:
return memo[target]
# found a valid sequence
if target == 0:
return 1
# not possible, exit
if target < 0:
return 0
# start counting # of sequences for the current target
cnt = 0
for num in nums:
if num > target:
continue
cnt += self.dfs(nums, target - num, memo)
memo[target] = cnt
return cnt
Solution (DP)
class Solution:
def combinationSum4(self, nums: List[int], target: int) -> int:
if not nums:
return 0
dp = [0] * (target + 1)
dp[0] = 1
for j in range(1, target + 1):
for num in nums:
if num > j:
continue
dp[j] += dp[j - num]
# nums: [3,1,2,4]
# target: 4
# dp: [1, 1, 2, 4, 8]
return dp[target]