本文主要是介绍夸父追日：第七章 回溯算法part03，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
今日收获：复原IP地址，子集，子集Ⅱ
1. 复原IP地址
题目链接：93. 复原 IP 地址 - 力扣（LeetCode）
思路：
1. 终止条件：因为整个字符串切割为四段就好，所以终止条件是path的长度为3，然后判断剩下字符串的有效性，如果有效就添加，无效就返回。
2. 和分割回文子串的思路相似，只是终止条件不同，以及判断字符串是否合法不同
方法：
class Solution {List<String> result=new ArrayList<>();List<String> path=new ArrayList<>();public List<String> restoreIpAddresses(String s) {back(s,0,new StringBuilder());return result;}public void back(String str, int start, StringBuilder sb){int len=str.length();// 终止条件if (path.size()==3){ // 切成了四段if (isValid(str.substring(start))){// 将path组合为ip地址形式StringBuilder stringbuilder=new StringBuilder();for (String ip:new ArrayList<>(path)){stringbuilder.append(ip).append(".");}stringbuilder.append(str.substring(start));result.add(stringbuilder.toString());}return;}for (int i=start;i<len;i++){sb.append(str.charAt(i));String s1=sb.toString();// 剪枝if (!isValid(s1)){return;}path.add(s1);back(str,i+1,new StringBuilder());path.removeLast();}}public boolean isValid(String str){if ("0".equals(str)){return true;}if (str.matches("[1-9][0-9]{0,2}")){int num=Integer.parseInt(str);if (num>0&&num<=255){return true;}}return false;}
}2. 子集
题目链接：78. 子集 - 力扣（LeetCode）
思路：不需要终止条件收集叶子节点，而是在回溯函数开始时收集节点，就是收集到了树中的所有节点
方法：
class Solution {List<List<Integer>> result=new ArrayList<>();List<Integer> path=new ArrayList<>(); // 单个子集public List<List<Integer>> subsets(int[] nums) {back(nums,0);return result;}public void back(int[] nums,int start){result.add(new ArrayList<>(path)); // 记录所有的节点for (int i=start;i<nums.length;i++){path.add(nums[i]);back(nums,i+1);path.removeLast();}}
}总结：代码随想录中截取的
1. 组合问题和分割问题都是收集树的叶子节点，而子集问题是找树的所有节点。
2. 求取子集问题，不需要任何剪枝！因为子集就是要遍历整棵树。
3. 子集Ⅱ
题目链接：90. 子集 II - 力扣（LeetCode）
思路：把78题和40题联系起来就可以解决这道题。收集树的所有节点；对同一层的相同元素去重，同一个树枝上不同位置的重复元素不需要去重。记得数组要先排序，把相同元素放在一起。
方法：
class Solution {List<List<Integer>> result=new ArrayList<>();List<Integer> path=new ArrayList<>();public List<List<Integer>> subsetsWithDup(int[] nums) {int[] used=new int[nums.length];Arrays.sort(nums);for (int i=0;i<nums.length;i++){used[i]=0;}back(nums,0,used);return result;}public void back(int[] nums,int start,int[] used){result.add(new ArrayList<>(path));for (int i=start;i<nums.length;i++){// 跳过选取本层重复的元素if (i>0&&nums[i]==nums[i-1]&&used[i-1]==0){continue;}path.add(nums[i]);used[i]=1;back(nums,i+1,used);path.removeLast();used[i]=0;}}
}这篇关于夸父追日：第七章 回溯算法part03的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
