代码随想录三刷day26

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

前言

如果把 子集问题、组合问题、分割问题都抽象为一棵树的话，那么组合问题和分割问题都是收集树的叶子节点，而子集问题是找树的所有节点！

一、力扣40. 组合总和 II

class Solution {List<List<Integer>> res = new ArrayList<>();List<Integer> path = new ArrayList<>();boolean[] flag;public List<List<Integer>> combinationSum2(int[] candidates, int target) {flag = new boolean[candidates.length];Arrays.sort(candidates);fun(candidates,target,0,0);return res;}public void fun(int[] candidates, int target,int index, int sum){if(sum >= target){if(sum == target){res.add(new ArrayList<>(path));}return;}for(int i = index; i < candidates.length; i ++){if(i > 0){if(sum + candidates[i] > target){return;}if(candidates[i] == candidates[i-1] && !flag[i-1]){continue;}}path.add(candidates[i]);flag[i] = true;fun(candidates,target,i+1,sum+candidates[i]);path.remove(path.size()-1);flag[i] = false;}}
}

二、力扣131. 分割回文串

在这里插入代码片class Solution {List<List<String>> res = new ArrayList<>();List<String> path = new ArrayList<>();public List<List<String>> partition(String s) {fun(s,0);return res;}public void fun(String s, int index){if(index >= s.length()){res.add(new ArrayList<>(path));return;}for(int i = index; i < s.length(); i ++){if(flag(s,index,i)){String str = s.substring(index,i+1);path.add(str);}else{continue;}fun(s,i+1);path.remove(path.size()-1);}}public boolean flag(String str,int low, int high){for(int i = low, j = high; i < j ; i ++, j --){if(str.charAt(i) != str.charAt(j)){return false;}}return true;}
}

三、力扣93. 复原 IP 地址

class Solution {List<String> res = new ArrayList<>();List<String> path = new ArrayList<>();public List<String> restoreIpAddresses(String s) {fun(s,0);return res;}public void fun(String s,int index){if(index == s.length()){StringBuilder sb = new StringBuilder();for(String s1 : path){sb.append(s1).append(".");}sb.deleteCharAt(sb.length()-1);res.add(sb.toString());return;}for(int i = index; i < s.length(); i ++){String temp = s.substring(index,i+1);if(flag(i,s,temp)){path.add(temp);}else{continue;}fun(s,i+1);path.remove(path.size()-1);}}public boolean flag(int index,String s,String temp){if(temp.length() > 3){return false;}int a = Integer.parseInt(temp);if(path.size() >= 4 && index == s.length()-1){return false;}if(temp.length() == 2 && temp.charAt(0) == '0'){return false;}if(temp.length() == 3 && temp.charAt(0) == '0'){return false;}if(temp.length() == 3 && a > 255){return false;}if(index == s.length()-1 && path.size() != 3){return false;}return true;}
}

四、力扣78. 子集

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