【代码随想录训练营】【Day28】第七章｜回溯算法｜93.复原IP地址｜78.子集｜90.子集II

复原IP地址

题目详细：LeetCode.93

这道题与上一道练习题分割回文字符串十分详细，一样是涉及到分割字符串、判断字符串、递归与回溯的问题，所以这道题要解决的难点在于：

• 如何分割IP地址字符串
• 如何判断分割的IP地址是否合法
• 递归的结束条件要如何设置

首先解决“如何判断分割的IP地址是否合法”，我们要知道一个合格的IP的地址的要求，在这道题中的要求比较简单，只要满足：

• IP地址中号段可以为0，但不存在以0开头的号段
• IP地址长度为4个字节，每一个号段的长度为1个字节，即其大小空间为2⁸ = 256，每一个号段用十进制表示的范围为0～255

其次是“如何分割IP地址字符串”，这里的分割思路于分割回文字符串非常相似：

• 在分割的过程中，对每一次分割的号段字符串都进行合法性验证
  • 如果当前号段合法，在其后续插入分割符 ‘.’ ，然后进入递归，继续分割下一个号段
  • 如果当前号段不合法，说明在当前位置进行分割的话，已经是一个不合法的IP地址了，所以无需继续分割，直接break跳出当前循环。

最后是“递归的结束条件要如何设置”，观察IP地址的特点可知：

• 一个IP地址最多存在3个分割符 ‘.’

那么我们就可以递归参数中设置一个变量来记录分割符的数量，如果数量==3时，即说明该IP地址分割完毕。

不过需要注意，我们在之前的分割的过程中，是先判断字段合法之后再添加分割符，所以当分割符数量==3之后，还需要对最后的号段进行合法性验证，以此来判断待添加的IP地址是否真的合法；无论是否合法都要return，因为这是递归的结束条件。

Java解法（递归，回溯）：

class Solution {List<String> ans = new ArrayList<>();public boolean isVaild(String s, int begin, int end){if (begin >= end || (end - begin) > 3) {return false;}// 0开头的数字不合法if (s.charAt(begin) == '0' && begin != end - 1) { return false;}int num = 0;// 遇到非数字字符不合法for (int i = begin; i < end; i++) {if (s.charAt(i) > '9' || s.charAt(i) < '0') { return false;}num = num * 10 + (s.charAt(i) - '0');// 如果大于255了不合法if (num > 255) { return false;}}return true;}public void backtracking(StringBuffer sb, int startIndex, int pointNums){if(pointNums == 3){if(isVaild(sb.toString(), startIndex, sb.length()))ans.add(sb.toString());return;}for(int i = startIndex; i < sb.length(); i++){if(isVaild(sb.toString(), startIndex, i + 1)){sb.insert(i + 1, '.');pointNums++;backtracking(sb, i + 2, pointNums);sb.deleteCharAt(i + 1);pointNums--;}else continue;}}public List<String> restoreIpAddresses(String s) {if(!(s.length() > 12 || s.length() < 4)){backtracking(new StringBuffer(s), 0, 0);}return this.ans;}
}

---

子集

题目详细：LeetCode.78

经过前面那些一知半解的练习之后，到了这道题，我终于领悟到了如何去打开回溯的解题思路，当遇到回溯问题时，我们立刻将问题转化都树形结构，开始画图（必须画图来理解，除非你空间想象力真的很好，我一开始凭空想了很久，但很容易乱，决定画图之后，发现一切都十分明辽了）：

画得非常草稿化，从前面回溯的理论基础和回溯解题模版可知：

• 回溯问题其实就是一个收集树形结构节点结果或路径结果的问题
• 循环的次数决定了树的宽度，相当于对树进行同层访问
• 递归的层数，就是循环的嵌套层数，相当于对树进行深度访问
• 递归的结束条件，就是回溯的条件，相当于访问到树的叶子节点

回到这道题，我们将问题转换为树形结构后，对应的就可以发现：

• 一个数字也可以是一个子集，所以在每次循环中，只取一个数字，可以定一个变量 start 来标识当前应该取哪个下标的数字
• 要求不能包含重复的子集，所以在进入递归时，要将当前的数字包括其之前的数字都分割出去，这里我们利用下标变量 start 来控制从数字开始访问
• 每访问一个节点，其路径上的节点集合，就是一个结果，所以要在循环和遍历过程中就将结果加入结果集
• 当nums数组为空时，即下标到达数组边界 start == nums.length 时，就是递归的结束条件，即回溯的条件

Java解法（递归，回溯）：

class Solution {List<List<Integer>> ans = new ArrayList<>();Deque<Integer> path = new ArrayDeque<>();public void backTrack(int[] nums, int start){if(nums.length == start){return;}for(int i = start; i < nums.length; i++){path.offer(nums[i]);ans.add(new ArrayList<Integer>(path));backTrack(nums, i + 1);path.removeLast();}}public List<List<Integer>> subsets(int[] nums) {ans.add(new ArrayList<Integer>());this.backTrack(nums, 0);return this.ans;}
}

---

子集II

题目详细：LeetCode.90

这道题与上一题的区别在于：整数数组nums可能包含重复的元素，依旧是要求返回不重复的子集集合。

那么其实就是在上一题的基础上，在树形结构上进行剪枝，达到在循环和递归过程中进行去重的目的，这样类似的题目在之前也有做过：【Day27】第七章｜回溯算法｜39. 组合总和｜40.组合总和II

是首先画图辅助理解：

通过之前的练习，我知道在递归结束时再进行去重操作中，在这一题同样会出现超出时间限制的情况，所以在这里就不重蹈覆辙了，所以难点就时如何在循环和递归的过程中，就对结果进行去重。

通过画图我们可以发现，去重操作或者说如何去判断是否会出现重复的结果，都是在树的同一层中进行处理的：

• 在循环过程中，当我们依次访问数组中的元素时，如果前一个元素与当前元素相等，那么我们再对当前元素进行递归操作的话，就有可能出现与前一个元素同样的子集
• 为什么说是有可能呢，而不是一定呢，因为可能还存在着如图中 [1, 2, 2] 这样带有重复元素的子集，所以为了避免丢失了部分子集，我们需要提前对数组进行排序，使其相同大小的数字都是连续的
• 同时也说明了去重操作需要在树的宽度访问中进行，而不是在树的深度访问中进行，也就是在进入递归前就进行去重判断
• 在这一道题中，我们可以利用一个布尔数组used来辅助去重
  • 当 nums[i] == nums[i - 1] && used[i] == true 时，说明虽然前一个数字已被访问，但是还未被回溯，进一步说明在树形结构中，当前路径还未到达叶子节点，在路径上还可能存在其他子集结果，需要继续递归到下一层
  • 当 nums[i] == nums[i - 1] && used[i] == false 时，说明虽然前一个数字与当前数字相同，但是由于递归是深度优先遍历，所以前一个数字之所以是 used[i - 1] == false ，是因为它已经被回溯了，其所有路径上的子集都已添加进结果集，如果再对当前数字继续递归的话，则会出现与前一个数字重复的子集，所以不需要在对当前数字进行递归，直接进入下一层循环

Java解法（递归，回溯，哈希）：

class Solution {List<List<Integer>> ans = new ArrayList<>();Deque<Integer> path = new ArrayDeque<>();public void backTrack(int[] nums, boolean[] used, int startIndex){if(nums.length == startIndex){return;}for(int i = startIndex; i < nums.length; i++){if(i > 0 && nums[i] == nums[i - 1] && !used[i - 1]){continue;}path.offer(nums[i]);used[i] = !used[i];ans.add(new ArrayList<Integer>(path));backTrack(nums, used, i + 1);path.removeLast();used[i] = !used[i];}}public List<List<Integer>> subsetsWithDup(int[] nums) {boolean[] used = new boolean[nums.length];Arrays.sort(nums);this.ans.add(new ArrayList<Integer>());this.backTrack(nums, used, 0);return this.ans;}
}

---

第一次接触到回溯，这两天做题总是停留在一知半解的地步，懵懵懂懂的，本来想要囫囵吞枣，得过且过算了，没想到最后两道练习题我突然醒悟，遇见回溯题就应该先将其转换为树形结构，通过画图来辅助理解整个循环、递归与回溯的过程，这入门的过程是如此的艰难，但是思路打开之后，一切都变得那么的通透了，真叫人：

初极狭，才通人，步行数十步，豁然开朗。