力扣爆刷第124天之回溯五连刷（分割回文、复原IP、子集）

一、131. 分割回文串

题目链接：https://leetcode.cn/problems/palindrome-partitioning/description/
思路：常规组合题，需要起始位置，然后只需要在向下递归的时候判断一下是否是回文，是回文就递归不是就不递归。

class Solution {List<List<String>> resList = new ArrayList<>();List<String> list = new ArrayList<>();public List<List<String>> partition(String s) {backTracking(s, 0);return resList;}void backTracking(String s, int index) {if(index == s.length()) {resList.add(new ArrayList(list));return ;}for(int i = index; i < s.length(); i++) {if(isTrue(s, index, i)) {list.add(s.substring(index, i+1));backTracking(s, i+1);list.remove(list.size()-1);}}}boolean isTrue(String s, int x, int y) {while(x < y) {if(s.charAt(x) != s.charAt(y)) {return false;}x++;y--;}return true;}
}

二、93. 复原 IP 地址

题目链接：https://leetcode.cn/problems/restore-ip-addresses/description/
思路：也是典型的组合问题，和上一题类似，都需要在向下递归的时候进行元素是否需要收集的判断，需要的话才递归。

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

三、78. 子集

题目链接：https://leetcode.cn/problems/subsets/description/
思路：常规组合，元素无重，只不过收集节点时，需要收集全部节点，包括非叶子节点和叶子节点。

class Solution {List<List<Integer>> resList = new ArrayList<>();List<Integer> list = new ArrayList<>();public List<List<Integer>> subsets(int[] nums) {backTracking(nums, 0);return resList;}void backTracking(int[] nums, int start) {resList.add(new ArrayList(list));for(int i = start; 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/
思路：和上一题类似，不同的地方是集合有重复元素，但好消息是可以排序，这样就可以横向去重，利用相邻元素相同。
相同的地方就是都是全部节点收集。

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

五、91. 非递减子序列

题目链接：https://leetcode.cn/problems/non-decreasing-subsequences/description/
思路：求非递减子序列，不能排序，集合有重复元素，要达到横向去重，需要使用set，每次递归向下都是一个新的set，横向for循环是同一个。

class Solution {List<List<Integer>> resList = new ArrayList<>();List<Integer> list = new ArrayList<>();public List<List<Integer>> findSubsequences(int[] nums) {backTracking(nums, 0);return resList;}void backTracking(int[] nums, int start) {if(list.size() > 1) {resList.add(new ArrayList(list));}Set<Integer> set = new HashSet<>();for(int i = start; i < nums.length; i++) {if(list.size() > 0 && nums[i] < list.get(list.size()-1)) continue;if(set.contains(nums[i])) continue;set.add(nums[i]);list.add(nums[i]);backTracking(nums, i+1);list.remove(list.size()-1); }}
}