93.复原IP地址
题目链接：力扣
思路
这道题目很重要，很多厂的面试题中都出现了，字节、虾皮、携程…… 与 131.分割回文串 相似，在添加结果的时候，需要判断所添加结果的合法性
切割问题的回溯搜索的过程和组合问题的回溯搜索的过程是差不多的，可以将切割问题抽象成组合问题，题目中细节很多，要注意，这道题要多敲
需要注意的点有：
1、判断所截取数字的合法性
以0开头的数字不合法
有非正整数字符不合法
大于255不合法
2、因为添加了逗点，递归时参数的变化
3、字符串回溯时的操作
4、切割线 startIndex
5、终止条件使用 逗点的数量进行控制 也就是树递归的深度
6、终止条件中还需要对最后一段数字进行判断
复原IP地址
class Solution { List<String> result = new ArrayList<>(); public List<String> restoreIpAddresses(String s) { // 剪枝操作 if (s.length() > 12) { return result; } backtracking(s,0,0); return result; } // 回溯函数 // startIndex: 搜索的起始位置 pointNum:添加逗点的数量----控制递归的深度，逗点为3的时候就代表可以收割了，但还是要判断一下最后一个逗点后面字符串的合法性 void backtracking (String s, int startIndex, int pointNum) { if (pointNum == 3) { // 逗点为3的时候，分隔结束 // 判断最后的子字符串是否合法，如果合法就收割 // 这里判断合法传入的是左闭右闭 if (isValid(s,startIndex,s.length()-1)) { result.add(s); } return; } for (int i = startIndex; i < s.length(); i++) { if (isValid(s,startIndex,i)) { // 在切割出来的子字符串的后⾯插⼊⼀个逗点 s = s.substring(0 , i + 1) + "." + s.substring(i + 1); pointNum++; // 递归 backtracking(s,i+2,pointNum); // 因为上面插入了一个逗点，所以下一个子串的起始位置为i+2 // 回溯 s = s.substring(0 , i + 1) + s.substring(i + 2); // 回溯删掉逗点 pointNum--; } else { break; } } } // 字符合法判断 判断字符串s在左闭⼜闭区间[start, end]所组成的数字是否合法 private Boolean isValid(String s,int start,int end) { if (start > end) { return false; } // 0 开头的数字不合法 if (s.charAt(start) == '0' && start != end) { return false; } // 遇到非法数字不合法 int num = 0; for (int i = start; i <= end; i++) { // 不在 0 和 9 之间的字符不合法 if (s.charAt(i) > '9' || s.charAt(i) < '0') { return false; } // 大于255的不合法 num = num * 10 + (s.charAt(i) - '0'); if (num > 255) { return false; } } return true; } }
78.子集
题目链接：力扣
思路
这道题目确实不难哈，子集问题是收集所有的树节点
如果把 子集问题、组合问题、分割问题都抽象为一棵树的话，那么组合问题和分割问题都是收集树的叶子节点，而子集问题是找树的所有节点！
本题中其实可以不需要加终止条件，因为startIndex >= nums.size()，本层for循环本来也结束了。
子集
class Solution { List<Integer> path = new ArrayList<>(); List<List<Integer>> result = new ArrayList<>(); public List<List<Integer>> subsets(int[] nums) { backtracking(nums,0); return result; } void backtracking(int[] nums,int startIndex) { // 这个位置真好 result.add(new ArrayList(path)); if (startIndex >= nums.length) { return; } for (int i = startIndex; i < nums.length; i++) { path.add(nums[i]); backtracking(nums,i + 1); path.remove(path.size() - 1); } } }
90.子集II
题目链接：力扣
思路
和 40 组合总和|| 力扣 是一个套路，也是树层去重 ，给定集合中是有重复元素的，但是结果中不能有重复的集合，给定数组中如果有重复的元素，按照之前的思路肯定是会有重复的结果的
所以一定要对收集的结果进行去重，使用used[] 数组标记每个元素的使用情况，对树层和树枝的重复进行区分
子集||
class Solution { List<Integer> path = new ArrayList<>(); List<List<Integer>> result = new ArrayList<>(); // 去重使用used数组 boolean[] used; public List<List<Integer>> subsetsWithDup(int[] nums) { if (nums.length == 0) { result.add(path); return result; } // 对数组进行排序 Arrays.sort(nums); // 填充used数组 used = new boolean[nums.length]; Arrays.fill(used,false); backtracking(nums,0); return result; } void backtracking(int[] nums, int startIndex) { result.add(new ArrayList<>(path)); if (startIndex >= nums.length) { return; } for (int i = startIndex; i < nums.length; i++) { if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) { continue; } path.add(nums[i]); used[i] = true; backtracking(nums,i + 1); path.remove(path.size() - 1); used[i] = false; } } }
总结
93.复制IP地址 这道题目和 131.分割回文串 原理上是一样的，只不过93比131处理起来比较复杂，是常考的面试题，因为既考察了回溯，也考察了对字符串的掌握情况
78.子集 跟组合问题不同的，只是组合问题和分割问题都是在叶子节点的时候收集结果，而子集问题是收集每种结果
90.子集|| 是78 和 40 的结合题，主要的难点在于去重，使用used区分树层去重和树枝去重
