DB真题 2020-06-18 40. Combination

https://leetcode.com/problems/combination-sum-ii/
字节跳动真题：数组、回溯、递归、

My answer / AC

/**
 * @param {number[]} candidates
 * @param {number} target
 * @return {number[][]}
 */

var combinationSum2 = function(candidates, target) {
    candidates = candidates.sort();
    var path = [];
    var res = [];
    dfs_com(candidates, 0, target, path, res);
    return res;
}

function dfs_com(cand, cur, target, path, res) {
    if(target == 0) {
        res.push(path.slice());
        return;
    }
    if(target<0) return; //只要target小于0就在这里截至
    for(var i=cur; i<cand.length; i++){
        if(i>cur && cand[i]==cand[i-1]) continue;
        path.push(cand[i]);
        dfs_com(cand, i+1, target-cand[i], path, res);
        path.pop();
    }
}

抄java的solution的0_0
每天问自己：深度遍历，我学会了吗！！

Best Solution

/**
 * @param {number[]} candidates
 * @param {number} target
 * @return {number[][]}
 */
var combinationSum2 = function(candidates, target) {
    candidates.sort((a,b)=>a-b);
    
    let res = [];
    let dfs = function(id, n, comb) {
        if (n == 0) {
            res.push(comb);
            return;
        }
        
        for (let i=id;i<candidates.length;i++) {
            if (candidates[i] <= n) { //在这里判断以防止传入小于0的target
                dfs(i+1, n - candidates[i], [...comb, candidates[i]]);
            }
            while(candidates[i+1]==candidates[i])i++;
        }
        return res;
    }
    
    dfs(0, target, []);
    return res;
};

原理都是一模一样的，都是在当前的哪个之后实现深度遍历。但是这个写法要优雅许多。

然而在防止target<0的处理上，前面的那个写法性能要稍微好一点点。

Recap

只能反复练练了。。。