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

回溯part04

93. 复原 IP 地址

组合问题（分割问题）

调试了两次，第一是是边界值cn没有弄正确，如果初始取1的话，只有在等于5的时候才会退出，下面这个是改过了，初始取0

/**
 * @param {string} s
 * @return {string[]}
 */
// 25525511135
// 分割问题
var restoreIpAddresses = function(s) {
    let res = [];
    backtracking(s, 0, res, 0, "");
    return res;
};

//只能分割4次
//cn为分割次数
function backtracking(s, startIndex, res, cn, ipAddress) {
    if(startIndex == s.length && cn == 4){//分割到尾巴了,且正好分割了四次
        res.push(ipAddress);
        return;
    }
    if(cn > 4) return;

    //取以starIndex开头，以i结尾的字符串（i取不到，所以这里的i可以遍历到length，而不是length-1）
    for(let i = startIndex + 1; i <= s.length && i <= startIndex + 3; i++){
        let subStr = s.slice(startIndex, i);
        //判断子串是否合法
        //不合法
        if(!isLegal(subStr)) continue;
        //合法
        if(cn == 0) backtracking(s, i, res, cn + 1, ipAddress + subStr);
        else backtracking(s, i, res, cn + 1, ipAddress + '.' +  subStr);
    }
}

function isLegal(str){
    if(str[0] == '0' && str.length != 1) return false;
    if(Number(str) > 255) return false;
    return true;
}

78. 子集

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var subsets = function(nums) {
    let res = [];
    backtracking(nums, 0, [], res);
    return res;
};
//迭代的深度是不固定的,在迭代的深度，即子集的长度没有到达num.length之前都不需要return
function backtracking(nums, startIndex, path, res) {
    if(path.length < nums.length){
        res.push([...path]);
    }else if(path.length == nums.length){
        res.push([...path]);
        return;
    }
    
    for(let i = startIndex; i < nums.length; i++){
        path.push(nums[i]);
        backtracking(nums, i + 1, path, res);
        path.pop();
    }
    return;
}

90. 子集 II

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var subsetsWithDup = function(nums) {
    let res = [];
    //要去重一定要记得先排序
    nums.sort();
    let used = new Array(nums + 1).fill(0);
    backtracking(nums, 0, [], res, used);
    return res;
};

function backtracking(nums, startIndex, path, res, used) {
    if(path.length <= nums.length){
        res.push([...path]);
    }
    if(path.length >= nums.length) return;
    
    for(let i = startIndex; i < nums.length; i++){
        //如果当前元素和其的前一个元素值一样的话
        //如果此时是在层间（即在回溯后的节点上）
        //如果前一个节点没有被使用，那么就是回溯的节点上
        //此时，应该直接跳过，因为值相同
        if(i > 0 && nums[i] === nums[i - 1]){
            if(!used[i-1]) continue;
        }
        path.push(nums[i]);
        used[i] = true;
        backtracking(nums, i + 1, path, res, used);
        used[i] = false;
        path.pop();
    }
    return;
}