代码随想录算法训练营第29天|回溯

回溯part05

491. 非递减子序列

这里的去重逻辑很巧妙

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var findSubsequences = function(nums) {
    let res = [];
    backtracking(nums, 0, [], res);
    return res;
};

function backtracking(nums, startIndex, path, res) {
    if(path.length > 1){
        res.push([...path]);
    }
    if(startIndex >= nums.length) return;
    let used = new Set();
    for(let i = startIndex; i < nums.length; i++){  
        if(path.length && nums[i] < path[path.length - 1]) continue;
        else if(used.has(nums[i])) continue;
        path.push(nums[i]);
        used.add(nums[i]);
        backtracking(nums, i + 1, path, res);
        path.pop();
    }
}

46. 全排列

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
 //排列
var permute = function(nums) {
    let res = [];
    backtracking(nums, res, []);
    return res;
};

function backtracking(nums, res, path) {
    if(path.length === nums.length){
        res.push([...path]);
        return;
    }

    for(let i = 0; i < nums.length; i++){
        if(path.indexOf(nums[i]) != -1) continue;//枝条去重
        path.push(nums[i])
        backtracking(nums, res, path);
        path.pop();
    }
}

47. 全排列 II

层间是for循环

枝条是迭代选择下去的

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var permuteUnique = function(nums) {
    let res = [];
    nums.sort();
    let used = new Array(nums.length + 1).fill(0);
    backtracking(nums, [], res, used)
    return res;
};

function backtracking(nums, path, res, used) {
    if(path.length === nums.length){
        res.push([...path]);
        return;
    }
    for(let i = 0; i < nums.length; i++){
        //在一个枝条上，第i个元素已经被使用，就直接跳过第i个元素
        if(used[i]) continue;
        //在层间，如果有相同的值的元素，直接跳过
        if(i > 0 && nums[i - 1] === nums[i] && !used[i - 1]) continue;
        path.push(nums[i]);
        used[i] = 1;
        backtracking(nums, path, res, used);
        path.pop();
        used[i] = 0;
    }
}