代码随想录 25（回溯算法 模板）
目录
回溯算法模板
力扣 93.复原IP地址
分析
解法
优化
力扣 78.子集
分析
解法
优化
回溯算法模板
void backtracking(参数) { if (终止条件) { 存放结果; return; } for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) { 处理节点; backtracking(路径，选择列表); // 递归 回溯，撤销处理结果 } }力扣 93.复原IP地址
分析
切割也是一种组合问题，类似里面的代码随想录 Day-19（回溯算法）-CSDN博客中分割回文串。
这里传入参数肯定需要一个startIndex，因为是不可重复。然后对于条件的校验可以用于一个函数封装起来。开始回溯三步骤。
毋庸置疑，无返回参数，然后传入参数肯定是s和startIndex。那么终止条件足够了吗？是否可以用哪个startIndex作为终止条件的判断吗？不够，题明确要求只会分成4段，所以不能用切割线切到最后作为终止条件，而是分割的段数作为终止条件。因此需要额外一个变量pointNum记录 . 的数量。
List<String> result = new ArrayList<>(); // startIndex: 搜索的起始位置， pointNum:添加逗点的数量 void backTrack(String s, int startIndex, int pointNum)终止条件是当pointNum到达数量上限3，也就是分割为四段。最后一段还没有进行校验，这里添加结果之前需要校验合法性。
if (pointNum == 3) {// 逗点数量为3时，分隔结束 // 判断第四段⼦字符串是否合法，如果合法就放进result中 if (isValid(s,startIndex,s.length()-1)) { result.add(s); } return; }单层循环：startIndex是切割起始位置，for循环中的 i 是子串的末尾位置，查看【startIndex，i】是否达到合法性，达到就添加一个 . 进行切割。切割之后，下一轮的起始位置不是 i+1，是 i+2，还有点的位置。记得记录pointNum的个数。
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); pointNum --; s = s.substring(0, i+1) + s.substring(i+2); }else{ // 不符合条件进行下一轮循环 break; } }解法
List<String> res = new ArrayList<>(); private void backTracking(String s, Integer startIndex, Integer pointNum){ if (pointNum == 3) { if (isValid(s, startIndex, s.length()-1)) { res.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); pointNum --; s = s.substring(0, i+1) + s.substring(i+2); }else{ // 不符合条件进行下一轮循环 break; } } } // 从s.length()-1可知子串是左闭右闭区间 private boolean isValid(String s, Integer start, Integer end){ if (start > end) { return false; } if (s.charAt(start) == '0' && start != end) { return false; } int num = 0; for (int i = start; i <= end; i++) { if (s.charAt(i ) > '9' || s.charAt(i) < '0') { return false; } num = num * 10 + (s.charAt(i) - '0'); // 转换为数字比较 if (num > 255) { return false; } } return true; }优化
写出完整代码之后，检查是否可以有剪枝？当s的长度大于12小于4那么永远无法分割，不够长度或者长度太长。是否可以判断当前切割的子串长度大于4直接返回？可以在校验那里加入这个剪枝判断。
可以考虑将s转换为StringBuilder会优化。这里不做新的解法。
public List<String> restoreIpAddresses(String s) { // 剪枝 if (s.length() > 12 || s.length() < 4) { return new ArrayList<>(); } backTracking(s, 0, 0); return res; } private boolean isValid(String s, Integer start, Integer end){ if (start > end) { return false; } // 剪枝 if (end - start > 3) { return false; } …… }力扣 78.子集
分析
抽象为一棵树的时候，可以发现，以前解题是返回的叶子节点，现在不仅是需要叶子节点还需要非叶子节点。这里不可以重复，所以用到startIndex。
public List<List<Integer>> subsets(int[] nums) { res.add(new ArrayList<>()); backTracking(nums, 0); return res; } List<List<Integer>> res = new ArrayList<>(); List<Integer> path = new LinkedList<>(); private void backTracking(int[] nums, Integer startIndex) { if (startIndex < nums.length) { res.add(new ArrayList<>(path)); return; } for (int i = startIndex; i < nums.length; i++) { path.add(nums[i]); backTracking(nums, i + 1); path.removeLast(); } }但是博主在写完代码发现，怎么返回的是空字符，一直没有子集，好奇怪。debug不出来，直接就结束，后面手动计算发现，在第一次startIndex=0时候，就retrun结束了，返回空字符串。难怪debug没发现，原来直接就结束。所以应该更改终止条件。更改终止条件之后，res的add操作应该放在单层循环中才符合逻辑。
解法
public List<List<Integer>> subsets(int[] nums) { res.add(new ArrayList<>()); backTracking(nums, 0); return res; } List<List<Integer>> res = new ArrayList<>(); List<Integer> path = new LinkedList<>(); private void backTracking(int[] nums, Integer startIndex) { if (startIndex >= nums.length) { return; } for (int i = startIndex; i < nums.length; i++) { path.add(nums[i]); res.add(new ArrayList<>(path)); backTracking(nums, i + 1); path.removeLast(); } }优化
求取子集问题，不需要任何剪枝！因为子集就是要遍历整棵树。
可以加一个条件，当数组长度只有1个时，也就是边界值。那么快速的直接返回一个结果，不用进入回溯。
public List<List<Integer>> subsets(int[] nums) { res.add(new ArrayList<>()); if (nums.length == 1) { path.add(nums[0]); res.add(new ArrayList<>(path)); return res; } backTracking(nums, 0); return res; }