力扣labuladong一刷day67天回溯大集合

本文主要是介绍力扣labuladong一刷day67天回溯大集合，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

力扣labuladong一刷day67天回溯大集合

一、93. 复原 IP 地址

题目链接：https://leetcode.cn/problems/restore-ip-addresses/description/
思路：分割字符串和排序数字其实是差不多的，分割出来的IP地址是讲究顺序的，所以也不用考虑去重，正常回溯模板即可，另外就是剪枝早停，可以节省时间，截了3个数了，最后一个4位数超3位了直接停止，能节省不少时间。类始于之前的题目分割回文串，要求返回所有的分割方案，也是不需要去重的，分割aaa，为a,aa和aa,a这是两种分割方案。

class Solution {List<String> list;List<String> arrayList;public List<String> restoreIpAddresses(String s) {list = new ArrayList<>();arrayList = new ArrayList<>();backTracking(s, 0);return arrayList;}void backTracking(String s, int index) {if (list.size() == 4) {if (index == s.length()) {String join = String.join(".", list);arrayList.add(join);}return;}for (int i = index; i < s.length(); i++) {if (list.size() == 3 && i-index > 2) return;String temp = isTrue(s, index, i + 1);if (temp == null) continue;list.add(temp);backTracking(s, i+1);list.remove(list.size()-1);}}String isTrue(String s, int i, int j) {if (i == j-1) {return String.valueOf(s.charAt(i));}if (s.charAt(i) == '0' || j-i > 3) return null;String temp = s.substring(i, j);if (Integer.valueOf(temp) > 255) return null;return temp;}
}

二、78. 子集

题目链接：https://leetcode.cn/problems/subsets/description/
思路：子集问题求所有子集，元素不重复，要求子集也不重复，只需要index每次加一即可。另外求的是全部子集，故需要在所有节点搜集元素，而不是叶子节点。注意这一点即可。组合问题和分割问题都是收集树的叶子节点，而子集问题是找树的所有节点。

class Solution {List<Integer> list;List<List<Integer>> arrayLists;public List<List<Integer>> subsets(int[] nums) {list = new ArrayList<>();arrayLists = new ArrayList<>();backTracking(nums, 0);return arrayLists;}void backTracking(int[] nums, int index) {arrayLists.add(new ArrayList<>(list));for (int i = index; i < nums.length; i++) {list.add(nums[i]);backTracking(nums, i+1);list.remove(list.size()-1);}}
}

三、90. 子集 II

题目链接：https://leetcode.cn/problems/subsets-ii/description/
思路：本题的子集是如nums = [1,2,2]这种，包含重复元素，单个元素不可重复选，要求子集无重，不可重复选只需要index每次加一即可，要求子集无重，就需要横向去重，在同一个树层，相同的元素左边的孩子用了，右边的就不能用了，有一个技巧，需要排序，让相同的数都挨着，通过if (i > index && nums[i] == nums[i-1]) continue;进行跳过。

class Solution {List<List<Integer>> arrayLists;List<Integer> list;public List<List<Integer>> subsetsWithDup(int[] nums) {arrayLists = new ArrayList<>();list = new ArrayList<>();Arrays.sort(nums);backTracking(nums, 0);return arrayLists;}void backTracking(int[] nums, int index) {arrayLists.add(new ArrayList<>(list));for (int i = index; i < nums.length; i++) {if (i > index && nums[i] == nums[i-1]) continue;list.add(nums[i]);backTracking(nums, i+1);list.remove(list.size()-1);}}
}

这篇关于力扣labuladong一刷day67天回溯大集合的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---