代码随想录算法训练营第二十八天|● 93.复原IP地址 ● 78.子集 ● 90.子集II （JS写法）

93 复原IP地址

题目链接/文章讲解：https://programmercarl.com/0093.%E5%A4%8D%E5%8E%9FIP%E5%9C%B0%E5%9D%80.html
视频讲解：https://www.bilibili.com/video/BV1XP4y1U73i/
在这里插入图片描述

思路：

在这里插入图片描述

/**
 * @param {string} s
 * @return {string[]}
 */
var restoreIpAddresses = function(s) {
    const res = [];
    const path = [];
    const backTracking = (start) => {
        //终止条件
        if(path.length === 4 && start === s.length){ //片段满4段，切指针走到最后即耗尽所有字符
            res.push(path.join('.'));  //拼成字符串，加入解集
            return;  //返不返回都行，指针已经到头了，严谨来说还是返回
        }
        if(path.length === 4 && start < s.length){  //满4段，但字符没有耗尽，就不用再往下选了
            return;
        }
        //单层循环
        //枚举出三种选择，三种切割长度
        for(let len = 1;len <= 3;len++){ 
            //加上要切的长度如果越界了，就不能切割这个长度
            if(start + len - 1 >= s.length) return;
            //不能切出'0x'、'0xx'，但可以切出'0'，所以在这里限制len的大小
            if(len !== 1 && s[start] == '0') return;
            //当前选择切除的片段
            const str = s.substring(start,start+len);
            //不能超过255，注意这里要把字符串转为数字
            if(len === 3 && +str > 255) return;
            path.push(str);
            //基于当前选择，继续选择，更新指针（更新start）
            backTracking(start+len);
            path.pop();
        }
    }
    backTracking(0);
    return res;

};

整体的终止条件在一开始的if语句里面判断，这时候要考虑的是总体的终止条件。
一些细节的判断在for循环里面进行，这时候判断的是是否符合一些小条件。
进行回溯的时候要更新start，start后面加的就是for循环里面的变量。
for循环里面的变量会随每道题意进行变换。

78 子集

题目链接/文章讲解：https://programmercarl.com/0078.%E5%AD%90%E9%9B%86.html
视频讲解：https://www.bilibili.com/video/BV1U84y1q7Ci
在这里插入图片描述

思路1：在执行子递归之前，加入解集，即，在递归压栈前 “做事情”。

在这里插入图片描述
用 for 枚举出当前可选的数，比如选第一个数时：1、2、3 可选。
如果第一个数选 1，选第二个数，2、3 可选；
如果第一个数选 2，选第二个数，只有 3 可选（不能选1，产生重复组合）
如果第一个数选 3，没有第二个数可选
即，每次传入子递归的 index 是：当前你选的数的索引 + 1。
每次递归枚举的选项变少，一直递归到没有可选的数字，那就进入不了for循环，落入不了递归，整个DFS结束。
可见我们没有显式地设置递归的出口，而是通过控制循环的起点，使得最后递归自然结束。

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var subsets = function(nums) {
    const res = [];
    const path = [];
    const backTracking = (start) => {
        //进入子递归之前，加入解集
        res.push(path.slice());
        for(let i = start;i < nums.length;i++){
            path.push(nums[i]);
            backTracking(i+1);  //是i+1不是start+1，因为在每一次循环里面index是不变的，所以如果更改index会有重复子集
            path.pop();
        }
    }
    backTracking(0);
    return res;
};

思路2：逐个考察数字，每个数都选或不选。等到递归结束时，把集合加入解集。

const subsets = (nums) => {
  const res = [];

  const dfs = (index, list) => {
    if (index == nums.length) { // 指针越界
      res.push(list.slice());   // 加入解集
      return;                   // 结束当前的递归
    }
    list.push(nums[index]); // 选择这个数
    dfs(index + 1, list);   // 基于该选择，继续往下递归，考察下一个数
    list.pop();             // 上面的递归结束，撤销该选择
    dfs(index + 1, list);   // 不选这个数，继续往下递归，考察下一个数
  };

  dfs(0, []);
  return res;
};

90 子集Ⅱ

题目链接/文章讲解：https://programmercarl.com/0090.%E5%AD%90%E9%9B%86II.html
视频讲解：https://www.bilibili.com/video/BV1vm4y1F71J
在这里插入图片描述

思路：40.组合总和II 和 78.子集，本题就是这两道题目的结合

判断重复的痛40题，详解见https://blog.csdn.net/weixin_44776979/article/details/136854651
i - 1 >= start这个条件判断式的含义是：当前索引i减去1大于等于起始索引start时，表示当前元素nums[i]和它的前一个相邻元素nums[i - 1]不是相同的元素，即当前元素不与前一个元素重复。

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var subsetsWithDup = function(nums) {
    const res = [];
    const path = [];
    nums.sort((a,b) => a-b);
    const backTracking = (start) => {
        res.push(path.slice());
        for(let i = start;i<nums.length;i++){
            if(i - 1 >= start && nums[i - 1] == nums[i]){
                continue;
            }
            path.push(nums[i]);
            backTracking(i+1);
            path.pop();
        }
    }
    backTracking(0);
    return res;
};