代码随想录 day28_fremount的博客-爱代码爱编程

题一：复原IP地址

题目链接： 复原IP地址
解题思路： 任何回溯过程都可以看作成一个树形结构，要抽象成一个树形结构，必须弄清楚树层和树枝是怎么构建的，在此题里，我们通过分割的方式来获得目标ip地址，for循环就代表着树枝上的构建，递归回溯就代表树层上的构建，确定递归的参数和返回值，确定终止条件，确定单次递归逻辑。此题一言两语说不清楚，我觉得最应该注意的是分割和判断是否有效那一块。
解题代码：

var isValid = function (s) {
    if(s.length === 0)return
    if ((s.length !== 1 && s.startsWith('0')) || parseInt(s) > 255) return false;
    return true;
}
var restoreIpAddresses = function (s) {
    let result = [];
    let path = [];
    if(s.length < 4)return [];
    let backtrenking = function (s, startIndex) {
        if (path.length === 3) {
            if (isValid(s.slice(startIndex, s.length))) {
                let temp = JSON.parse(JSON.stringify(path));
                temp.push(s.slice(startIndex,s.length));
                result.push(temp.join(""));
            }
            return;
        }
        for (let i = startIndex + 1; i < s.length; i++) {
            if (isValid(s.slice(startIndex, i))) {
                path.push(s.slice(startIndex, i) + '.');
                console.log(path,startIndex,i);
                backtrenking(s, i);
                path.pop();
            }else{
                return;
            }
        }
    }
    backtrenking(s,0);
    return result;
};

题二：子集

题目链接： 子集
解题思路： 一开始我以为要用一个used，但是里边没有重复的数字，所以就没必要用了，抽象成一棵树之后就是简单的递归回溯。然后还有一点需要注意的是我们在遍历的过程中是边遍历遍收集结果的。
解题代码：

var subsets = function (nums) {
    let path = [];
    let result = [[]];
    let backtrenking = function(nums,startIndex){
        if(startIndex === nums.length){
            return;
        }
        for(let i = startIndex;i<nums.length;i++){
            path.push(nums[i]);
            let temp = JSON.parse(JSON.stringify(path));
            result.push(temp);
            backtrenking(nums,i+1);
            path.pop();
        }
    }
    backtrenking(nums,0);
    return result;
};

题三：子集II

题目链接： 子集II
解题思路： 这边儿就需要用到一个used数组了，需要特别注意的一点是在单次递归遍历的逻辑里边，如果这个数字和前面那个数相等，我们到底应不应该继续往下操作，结合卡尔哥的点拨，我知道当前面那个数没有被用过的时候就不可以往下遍历，应为那恰好是被用过回溯过来的，如果接着使用则一定会出现重复的数字，如果遍历过了的话则这次遍历肯定是在树枝上，可以往下继续进行。而且这还有一点需要注意就是要把给出的nums数组先进行排序。
解题代码：

var subsetsWithDup = function (nums) {
    let path = [];
    let result = [[]];
    let used = new Array(nums.length).fill(1);
    nums.sort((a,b)=>a-b)
    let backtrenking = function (nums, startIndex) {
        if (startIndex === nums.length) return;
        for (let i = startIndex; i < nums.length; i++) {
            if (i > 0 && nums[i - 1] === nums[i] && used[i - 1] === 1)continue;
            path.push(nums[i]);
            let temp = JSON.parse(JSON.stringify(path));
            result.push(temp);
            used[i] = 0;
            backtrenking(nums, i + 1);
            path.pop();
            used[i] = 1;
        }
    }
    backtrenking(nums, 0);
    return result;
};