代码随想录 25（回溯算法 模板）

目录回溯算法模板力扣 93.复原IP地址分析解法优化力扣 78.子集分析解法优化回溯算法模板void backtracking(参数) { if (终止条件) { 存放结果; return; } for (选择本层集合中元素树中节点孩子的数量就是集合的大小) { 处理节点; backtracking(路径选择列表); // 递归 回溯撤销处理结果 } }力扣 93.复原IP地址分析切割也是一种组合问题类似里面的代码随想录 Day-19回溯算法-CSDN博客中分割回文串。这里传入参数肯定需要一个startIndex因为是不可重复。然后对于条件的校验可以用于一个函数封装起来。开始回溯三步骤。毋庸置疑无返回参数然后传入参数肯定是s和startIndex。那么终止条件足够了吗是否可以用哪个startIndex作为终止条件的判断吗不够题明确要求只会分成4段所以不能用切割线切到最后作为终止条件而是分割的段数作为终止条件。因此需要额外一个变量pointNum记录 . 的数量。ListString 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 是子串的末尾位置查看【startIndexi】是否达到合法性达到就添加一个 . 进行切割。切割之后下一轮的起始位置不是 i1是 i2还有点的位置。记得记录pointNum的个数。for (int i startIndex; i s.length(); i) { if (isValid(s, startIndex, i)) { s s.substring(0, i1) . s.substring(i1); // 点的位置 pointNum ; backTracking(s, i2, pointNum); pointNum --; s s.substring(0, i1) s.substring(i2); }else{ // 不符合条件进行下一轮循环 break; } }解法ListString 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, i1) . s.substring(i1); // 点的位置 pointNum ; backTracking(s, i2, pointNum); pointNum --; s s.substring(0, i1) s.substring(i2); }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 ListString 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 ListListInteger subsets(int[] nums) { res.add(new ArrayList()); backTracking(nums, 0); return res; } ListListInteger res new ArrayList(); ListInteger 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不出来直接就结束后面手动计算发现在第一次startIndex0时候就retrun结束了返回空字符串。难怪debug没发现原来直接就结束。所以应该更改终止条件。更改终止条件之后res的add操作应该放在单层循环中才符合逻辑。解法public ListListInteger subsets(int[] nums) { res.add(new ArrayList()); backTracking(nums, 0); return res; } ListListInteger res new ArrayList(); ListInteger 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 ListListInteger 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; }