代码随想录算法训练营day28 || 93.复原IP地址，78.子集，90.子集II

?视频讲解：

回溯算法如何分割字符串并判断是合法IP？| LeetCode：93.复原IP地址_哔哩哔哩_bilibili

回溯算法解决子集问题，树上节点都是目标集和！ | LeetCode：78.子集_哔哩哔哩_bilibili

回溯算法解决子集问题，如何去重？| LeetCode：90.子集II_哔哩哔哩_bilibili

?93.复原IP地址

思路：有效 IP 地址?正好由四个整数（每个整数位于?0?到?255?之间组成，且不能含有前导?0），依据这个条件可以明确也是如何分割字符串一般是对不同长度的字串进行衡量，递归循环遍历时所构建是不同长度的字串，然后判断是否满足[0,255]条件。

// 时间复杂度O(3^4*k)，其中k是ans的长度，而每一种ip都是需要4个位置的一个或三个字符构成
// 空间复杂度O(k*(4*3+3))，是构建的列表保存所有ip地址所花费的开销

class Solution {
    List<String> ans = new ArrayList<>();
    List<String> list = new ArrayList<>();

    public List<String> restoreIpAddresses(String s) {
        if(s==null || s.equals(""))
            return ans;
        backtracking(s, 0, 0);
        for (String ip:ans) {
            System.out.println(ip);

        }
        return ans;
    }

    public void backtracking(String s, int begin, int count){
        // 终止条件
        if(count == 4 || begin == s.length()){
            if(begin == s.length() && count == 4){
                StringBuilder builder = new StringBuilder();
                for(String ss:list)
                    builder.append(ss+".");
                builder.deleteCharAt(builder.length()-1);
                ans.add(builder.toString());
            }
            return;
        }
        // 每个整数位于 0 到 255 之间组成，且不能含有前导 0

        // 出现前导0，则后续不可以再加入其他的元素
        if(s.charAt(begin) == '0'){
            list.add("0");
            backtracking(s, begin+1, count+1);
            list.remove(list.size()-1);
        }
        else{
            // 每个子串长度最多为3
            for(int i=0; i<begin+3 && begin+i<s.length(); i++){
                // 得到当前子串的结尾位置
                int end = begin+i+1;
                String str = s.substring(begin, end);
                
                // 判断当前子串是否满足ip范围
                int num = Integer.parseInt(str);
                if(num>0 && num<=255){
                    list.add(str);
                    backtracking(s, end, count+1);
                    list.remove(list.size()-1);
                }
            }
        }
        return;

    }
}

78.子集

思路：与求数组的组合思路基本一致。

// 时间复杂度最大是O(n^n)，节点所生成的树的高度最大是n，n也为nums的长度
// 空间复杂度最大是O(n^2)

class Solution {
    List<List<Integer>> ans = new ArrayList<>();
    List<Integer> list = new ArrayList<>();

    public List<List<Integer>> subsets(int[] nums) {
        // 返回所有的子集，子集区别于组合，组合有一个对比条件
        ans.add(new ArrayList<>());
        if(nums.length == 0)
            return ans;
        backtracking(nums, -1);
        return ans;
    }

    public void backtracking(int[] nums, int index){
        // 终止条件
        if(index >= nums.length-1)
            return;
        

        for(int i=index+1; i<nums.length; i++){
            list.add(nums[i]);
            if(list.size() <= nums.length)
                ans.add(new ArrayList<Integer>(list));
            backtracking(nums, i);
            list.remove(list.size()-1);
        }

        return;
    }
}

?90.子集II

思路：与存在重复的元素的组合|| 解法一致。

// 时间复杂度最大O(n^k)，n可以视作生成树的最大高度，k是数组中所有不重复的数字个数
// 空间复杂度最大O(kn)

class Solution {
    List<List<Integer>> ans = new ArrayList<>();
    List<Integer> list = new ArrayList<>();

    public List<List<Integer>> subsetsWithDup(int[] nums) {
        ans.add(new ArrayList<>());
        if(nums.length == 0)
            return ans;
        Arrays.sort(nums);
        boolean[] visited = new boolean[nums.length];
        backtracking(nums, 0, visited);
        return ans;
    }

    public void backtracking(int[] nums, int startindex, boolean[] visited){
        if(startindex == nums.length){
            return;
        }

        for(int i=startindex; i<nums.length; i++){
            // 去重
            if(i-1>=0 && nums[i] == nums[i-1] && visited[i-1] == false)
                continue;
            list.add(nums[i]);
            visited[i] = true;
            // 当前是可行子集
            if(list.size() <= nums.length)
                ans.add(new ArrayList<Integer>(list));
            backtracking(nums, i+1, visited);
            list.remove(list.size()-1);
            visited[i] = false;
        }
        return;
    }
}