377. Combination Sum IV

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)