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.
这道题最直观的做法就是递归搜索：
var combinationSum4 = function(nums, target) {
const totalLen = nums.length;
let result = 0;
const search = function(nums, target) {
for(let i=0;i<totalLen;i++) {
if(nums[i] === target) {
result++;
return;
}
else if(nums[i] < target) {
search(nums, target-nums[i]);
}
else {
return;
}
}
};
search(nums, target);
return result;
};
很是暴力直接，当target与数组里的元素差距不大时运行得非常好，但是遇到像是var nums = [1, 2, 3], target = 32;这样的测试用例时，会耗费2s左右的时间，耗时过长。回到题目中，有个解法提示，让我们考虑下动态规划。
例如用例为var nums = [1, 2, 3], target = 4;当计算target为3时，它的解法数量可以为dp[3] += dp[3-x]，也就是说3可以拆分为1+x，2+x，3+x，这里dp[x]表示target为x时的解法。那么对于i从1到target，如果i不小于nums中的数，则可以用dp[i] += dp[i-x]表示对应的解数。
上代码：
var combinationSum4 = function (nums, target) {
const dp = [1];
nums.sort((a, b) => { return a - b; })
for (let i = 1; i <= target; i++) {
dp.push(0);
for (let num of nums) {
if (num <= i) {
dp[i] += dp[i - num];
}
else {
break;
}
}
}
return dp[target];
};
时间复杂度为O(n^2)，空间复杂度O(n)
