Given an array of distinct integers nums and a target integer target, return the number of possible combinations that add up to target.
The answer is guaranteed to fit in a 32-bit integer.
Input: nums = [1,2,3], target = 4
Output: 7
Explanation:
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.
Input: nums = [9], target = 3
Output: 0
1 <= nums.length <= 200
1 <= nums[i] <= 1000
All the elements of nums are unique.
1 <= target <= 1000
We can use dynamic programming to create an array with a length of (1 + target) to store all the values. The time complexity would be O(N * M) and space complexity would be O(M) where N is the lenght of array nums and M is the target value.
def combinationSum4(nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: int
:Time Complexity: O(N * M)
:Space Complexity: O(M)
"""
dp = [0] * (target + 1)
dp[0] = 1
for i in range(1, target + 1):
for n in nums:
if i - n >= 0:
dp[i] += dp[i - n]
return dp[-1]