leetcode39

本周开启了回溯递归，打算按照简单中等顺序做。

找能组成target的所有组合，组合意味着顺序不同也是一个组合。

var combinationSum = function (candidates, target) {
            let res = new Array();
            candidates.sort((a, b) => {
                return a - b;
            })
            dfs([], 0, 0);

            function dfs(path, sum, index) {
                //终止条件 return; 表示什么也不做
                if (sum >= target) {
                    if (sum == target) {
                        res.push([...path]);
                    }
                    return;
                }
                // index是每次开始的位置
                for (let i = index; i < candidates.length; i++) {
                    
                    path.push(candidates[i]);
                    dfs(path, sum + candidates[i], i);
                    path.pop();
                }
            }
            return res;
        };

 这是后面的图，这里拿来用一用。因为每个数可以选择多次，for循环相当于横向遍历，dfs相当于进入下一层。比如先把2push进去，dfs探索下一层，index标明下一层梦开始的地方pop2标志着：此层的2旅行结束，继续横向遍历了。ok回到本题，数可以重复使用说明下一层梦开始的地方还是和本层一样，不可能在本层开始地方之前（这是组合）。

var combinationSum2 = function (candidates, target) {
    candidates.sort((a, b) => {
        return a - b;
    })
    res = new Array()
    function dfs(index, sum, path) {
        if (sum >= target) {
            if (sum == target)
                res.push([...path]);
            return;
        }
        for (let i = index; i < candidates.length; i++) {
            if ( candidates[i] == candidates[i - 1] && i>index) continue;
            path.push(candidates[i]);
            dfs(i+1,sum+candidates[i],path); //+1是因为不重复
            path.pop();
            
        }
    }
    dfs(0,0,[])
    return res;
};