代码随想录三刷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);
        }
    }
}