LeetCode Combination Sum题汇总-一一网

第零题

var combine = function(n, k) {
    let res = []
    helper([],1)
    return res

    function helper(arr, i) {
        if (arr.length==k) {
            res.push(arr)
            return
        }
        if (arr.length+(n-i+1)<k) return
        for (let j = i; j <= n; j++) {
            helper(arr.concat([j]), j+1)
        }
    }
};
复制代码

第一题

39. Combination Sum

var combinationSum = function(candidates, target) {
    let res = []
    candidates.sort((a,b)=>a-b)
    helper([],0,0)
    return res

    function helper(arr, sum, last_idx) {
        if (sum==target) {
            res.push(arr)
            return
        } else if (sum>target) return
        // 剪枝
        if (sum+candidates[last_idx]>target) return
        for (let i = last_idx; i < candidates.length; i++) {
            helper(arr.concat([candidates[i]]),sum+candidates[i], i)
        }
    }
};
复制代码

第二题

40. Combination Sum II

第一题的思路很简单，就是不断递归，每次都把整个candidates数组遍历一遍。但是它会有重复，如[1,2]和[2,1]，那么我们可以限定后面加进来的不能小于当前数组中最后一个数，这样即可重复使用同一个数字，也可以防止出现重复。

第二题与第一题不同之处在于这题的每个元素只能使用一次。乍一想直接回溯就行了呀，可是假如有这种情况candidates=[1,1,2]，第一个1的[1,2]和第二个1的[1,2]其实是重复的，因此我们在回溯的时候需要去重。第一个想法是记录每个数字出现次数，然后对每个数字出现[0,cnt]次的情况进行遍历，这种思路比较直观好理解。看了别人的解法，其实也很不错，回溯算法 + 剪枝；他的思路是把回溯过程看作一棵树，每一层push进一个数，然后下一层的数肯定在这个数后面(其实所有回溯过程都可以看作这样一棵树，所谓的剪枝就是将这棵树中一些重复的、不需要的部分剪掉)，同一层数值相同的结点第 22、33 … 个结点，因为数值相同的第 11 个结点已经搜索出了包含了这个数值的全部结果，这句话是这个算法去重的核心。

// 解法一
var combinationSum2 = function(candidates, target) {
    let res = []
    candidates.sort((a,b)=>a-b)
    let num_cnt = []
    let num = candidates[0], cnt = 1
    for (let i = 1; i < candidates.length; i++) {
        if (candidates[i]==num) cnt++
        else {
            num_cnt.push([num,cnt])
            num = candidates[i]
            cnt = 1
        }
    }
    num_cnt.push([num,cnt])
    helper([].slice(),0,0)
    return res

    function helper(arr,sum,idx) {
        if (sum==target) {
            res.push(arr)
            return
        } else if (idx>=num_cnt.length||sum>target) return
        let [num,cnt] = num_cnt[idx]
        if (sum+num>target) return
        helper(arr.slice(), sum, idx+1)
        for (let i = 1; i <= cnt; i++) {
            arr.push(num)
            sum += num
            if (sum>target) return
            helper(arr.slice(),sum,idx+1)
        }
    }
};
// 解法二
var combinationSum2 = function(candidates, target) {
    let res = []
    candidates.sort((a,b)=>a-b)
    helper([],0,0)
    return res

    function helper(arr,sum,idx) {
        if (sum==target) {
            res.push(arr)
            return
        } else if (idx>=candidates.length||sum>target) return
        for (let i = idx; i < candidates.length; i++) {
            if (sum+candidates[i]>target) return
            if (i>idx&&candidates[i]==candidates[i-1]) continue
            helper(arr.concat([candidates[i]]),sum+candidates[i],i+1)
        }
    }
};
复制代码

第三题

216. Combination Sum III

var combinationSum3 = function(k, n) {
    let res = []
    helper([],0,1)
    return res

    function helper(arr,sum,idx) {
        if (arr.length>k) return
        if (arr.length==k) {
            if (sum==n) res.push(arr)
            return
        }
        for (let i = idx; i <= 9; i++) {
            if (sum+i>n) return
            helper(arr.concat([i]),sum+i,i+1)
        }
    }
};
复制代码

第四题

377. Combination Sum IV

由于这里可以出现[1,1,2],[1,2,1]这种情况，因此我们现在不是每次从i开始下一层了，而是需要从第一个元素开始，经检验会超时。那么我们采用动态规划的解法吧。令dp[t]表示和为t的组合总数，对于nums中的每个num，dp[t]+=dp[t-num]。

var combinationSum4 = function(nums, target) {
    let dp = [1]
    for (let t = 1; t <= target; t++) {
        dp[t] = 0
        for (let num of nums) {
            if (t-num>=0) dp[t] += dp[t-num]
        }
    }
    return dp[target]
};
复制代码