本文主要是介绍Day27 代码随想录(1刷) 回溯，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
131. 分割回文串
给你一个字符串
s，请你将s分割成一些子串，使每个子串都是回文串
。返回s所有可能的分割方案。示例 1：
输入：s = "aab" 输出：[["a","a","b"],["aa","b"]]示例 2：
输入：s = "a" 输出：[["a"]]提示：
1 <= s.length <= 16s仅由小写英文字母组成
状态：完成
思路：目的是分割使每个子串都是回文串，所以用回溯来解决问题。用result来记录合理的分割方式，用path来装分割的子串，回溯中我们只要从startIndex开始就行了，每一次递归都判断该字串是否是回文串，是就继续不是就继续循环。
class Solution {List<List<String>> result=new ArrayList<>();LinkedList<String> path=new LinkedList<>();public List<List<String>> partition(String s) {backstracking(s,0);return result;}public void backstracking(String s,int startIndex){if(startIndex==s.length()){result.add(new ArrayList(path));}for(int i=startIndex;i<s.length();i++){String sub=s.substring(startIndex,i+1);if(isHui(sub)){path.add(sub);backstracking(s,i+1);path.removeLast();}}}public boolean isHui(String s){int left=0;int right=s.length()-1;while(left<right){if(s.charAt(left)!=s.charAt(right)){return false;}left++;right--;}return true;}
}93. 复原 IP 地址
有效 IP 地址 正好由四个整数（每个整数位于
0到255之间组成，且不能含有前导0），整数之间用'.'分隔。
- 例如：
"0.1.2.201"和"192.168.1.1"是 有效 IP 地址，但是"0.011.255.245"、"192.168.1.312"和"192.168@1.1"是 无效 IP 地址。给定一个只包含数字的字符串
s，用以表示一个 IP 地址，返回所有可能的有效 IP 地址，这些地址可以通过在s中插入'.'来形成。你 不能 重新排序或删除s中的任何数字。你可以按 任何 顺序返回答案。示例 1：
输入：s = "25525511135" 输出：["255.255.11.135","255.255.111.35"]示例 2：
输入：s = "0000" 输出：["0.0.0.0"]示例 3：
输入：s = "101023" 输出：["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]提示：
1 <= s.length <= 20s仅由数字组成
状态：完成，wa了一次。
思路：跟上一题差不多就是判断条件有区别，上一题是回文串这一题是判断这一部分是否不是0开始并且小于等于255.
class Solution {List<String> result=new ArrayList<>();StringBuilder sb=new StringBuilder();public List<String> restoreIpAddresses(String s) {sb.append(s);backstracking(0,0);return result;}public void backstracking(int startIndex,int level){String temp=sb.substring(startIndex,sb.length());if(level==3){temp=sb.substring(startIndex,sb.length());if(temp.length()==0||temp.length()>3) return;if(temp.startsWith("0")&&temp.length()>1) return;if(Integer.valueOf(temp)>255) return;result.add(sb.toString());}for(int i=1;startIndex+i<=sb.length()&&i<=3;i++){temp=sb.substring(startIndex,startIndex+i);if(i>1&&temp.startsWith("0")) break;if(Integer.valueOf(temp)>255) break;sb.insert(startIndex+i,".");backstracking(startIndex+i+1,level+1);sb.replace(startIndex+i,startIndex+i+1,"");}}
}78. 子集
给你一个整数数组
nums，数组中的元素 互不相同 。返回该数组所有可能的子集
（幂集）。解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
示例 1：
输入：nums = [1,2,3] 输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]示例 2：
输入：nums = [0] 输出：[[],[0]]提示：
1 <= nums.length <= 10-10 <= nums[i] <= 10nums中的所有元素 互不相同
状态：完成
思路：求该数组的所有的子集，所以我们回溯的时候要传递一个startIndex的参数来限制，回溯结束的条件就是startIndex>=nums.length说明这时候就走到头了，跟之前的不一样他要求所有的子集所以每次添加之后直接放进结果数组中。
class Solution {List<List<Integer>> result=new ArrayList<>();LinkedList<Integer> list=new LinkedList<>();public List<List<Integer>> subsets(int[] nums) {result.add(new ArrayList(list));backstracking(0,nums);return result;}public void backstracking(int startIndex,int[] nums){if(startIndex>=nums.length) return;for(int i=startIndex;i<nums.length;i++){list.add(nums[i]);result.add(new ArrayList(list));backstracking(i+1,nums);list.removeLast();}}
}90. 子集 II
给你一个整数数组
nums，其中可能包含重复元素，请你返回该数组所有可能的子集
（幂集）。解集 不能 包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。
示例 1：
输入：nums = [1,2,2] 输出：[[],[1],[1,2],[1,2,2],[2],[2,2]]示例 2：
输入：nums = [0] 输出：[[],[0]]提示：
1 <= nums.length <= 10-10 <= nums[i] <= 10
状态：完成
思路：跟之前求和那题一样，只要使用used数组去做树层去重的判断就可以了。
class Solution {List<List<Integer>> result=new ArrayList<>();List<Integer> list=new LinkedList<>();public List<List<Integer>> subsetsWithDup(int[] nums) {Arrays.sort(nums);result.add(new LinkedList());backstracking(0,new boolean[nums.length],nums);return result;}public void backstracking(int startIndex,boolean[] used,int[] nums){if(startIndex>=nums.length) return;for(int i=startIndex;i<nums.length;i++){if(i>0&&nums[i-1]==nums[i]&&used[i-1]){used[i]=true;continue;}System.out.println(startIndex+" "+i+" "+list);list.add(nums[i]);used[i]=true;result.add(new LinkedList(list));backstracking(i+1,new boolean[nums.length],nums);list.removeLast();}}
}感想：重做回溯感觉良好，加快速度争取后天刷完。
这篇关于Day27 代码随想录(1刷) 回溯的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
