Problem
Given an array of distinct integers nums and a target integer target, return the number of possible combinations that add up to target.
The test cases are generated so that the answer can fit in a 32-bit integer.
Example 1:
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.
Example 2:
Input: nums = [9], target = 3
Output: 0
Constraints:
1 <= nums.length <= 2001 <= nums[i] <= 1000All the elements of
numsare unique.1 <= target <= 1000
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
/**
* @param {number[]} nums
* @param {number} target
* @return {number}
*/
var combinationSum4 = function(nums, target, map = {}) {
if (target === 0) return 1;
if (map[target] !== undefined) return map[target];
var res = 0;
for (var i = 0; i < nums.length; i++) {
if (nums[i] > target) continue;
res += combinationSum4(nums, target - nums[i], map);
}
map[target] = res;
return res;
};
Explain:
Top-down dynamic programming.
Complexity:
- Time complexity : O(target).
- Space complexity : O(target * n).