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;
};
很是暴力直接，當(dāng)target與數(shù)組里的元素差距不大時運(yùn)行得非常好，但是遇到像是var nums = [1, 2, 3], target = 32;這樣的測試用例時，會耗費2s左右的時間，耗時過長。回到題目中，有個解法提示，讓我們考慮下動態(tài)規(guī)劃俊庇。
例如用例為var nums = [1, 2, 3], target = 4;當(dāng)計算target為3時狮暑，它的解法數(shù)量可以為dp[3] += dp[3-x]，也就是說3可以拆分為1+x辉饱，2+x搬男，3+x，這里dp[x]表示target為x時的解法彭沼。那么對于i從1到target缔逛，如果i不小于nums中的數(shù)，則可以用dp[i] += dp[i-x]表示對應(yīng)的解數(shù)姓惑。
上代碼：
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];
};
時間復(fù)雜度為O(n^2)褐奴，空間復(fù)雜度O(n)
