day28 回溯算法part4

93. 复原 IP 地址

中等
有效 IP 地址正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 ‘.’ 分隔。
例如：“0.1.2.201” 和 “192.168.1.1” 是有效 IP 地址，但是 “0.011.255.245”、“192.168.1.312” 和 “192.168@1.1” 是无效 IP 地址。
给定一个只包含数字的字符串 s ，用以表示一个 IP 地址，返回所有可能的有效 IP 地址，这些地址可以通过在 s 中插入 ‘.’ 来形成。你不能重新排序或删除 s 中的任何数字。你可以按任何顺序返回答案。

class Solution {
    List<String> res = new LinkedList<>();
    LinkedList<String> path = new LinkedList<>();

    public List<String> restoreIpAddresses(String s) {
        backtrack(s, 0);
        return res;
    }

    public void backtrack(String s, int start) {
        if(path.size() == 4 && start == s.length()) {
            res.add(String.join(".", path));
           
        }
        for (int i = start; i < s.length(); i++) {
            if (!isValid(s, start, i)) { // 判断这段数字合不合法
                continue;
            }
            if(path.size() >= 4) break; // 已经分解成 4 部分了，不能再分解了
            // 如果合法，加入路径
            path.add(s.substring(start, i + 1));
            // 继续向右切
            backtrack(s, i + 1);
            // 撤销加入
            path.remove(path.size() - 1);
        }
    }
    // 判断字符串s在左闭右闭区间[start, end]所组成的数字是否合法
    boolean isValid(String s, int start, int end) {
        if (start > end) return false;
        // 0开头的数字不合法, 除非是 ‘0’
        if (s.charAt(start) == '0' && start != end) return false;
    
        int num = 0;
        for (int i = start; i <= end; i++) {
            // 遇到⾮数字字符不合法（好像不用判断）
            if (s.charAt(i) > '9' || s.charAt(i) < '0') { 
                return false;
            }
            num = num * 10 + (s.charAt(i) - '0');
            if (num > 255) return false;  // 如果⼤于255了不合法
        }
        return true;
    }
}

78. 子集

中等
给你一个整数数组 nums ，数组中的元素互不相同。返回该数组所有可能的子集（幂集）。
解集不能包含重复的子集。你可以按任意顺序返回解集。
在这里插入图片描述

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    List<Integer> path = new ArrayList<>();

    public List<List<Integer>> subsets(int[] nums) {
        backtrack(nums, 0);
        return res;
    }

    public void backtrack(int[] nums, int start) {
        res.add(new ArrayList<>(path));
        if (path.size() == nums.length) return; //可以不写


        for (int i = start; i < nums.length; i++) {
            path.add(nums[i]);
            backtrack(nums, i + 1); //backtrack(nums, start + 1);总是写成这个！！！
            path.remove(path.size() - 1);
        }
        return;
    }
}

90. 子集 II

中等
给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。
解集不能包含重复的子集。返回的解集中，子集可以按任意顺序排列。
在这里插入图片描述

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    List<Integer> path = new ArrayList<>();

    public List<List<Integer>> subsetsWithDup(int[] nums) {
        Arrays.sort(nums);
        backtrack(nums, 0);
        return res;
    }

    public void backtrack(int nums[], int start) {

        res.add(new ArrayList<>(path));
        for (int i = start; i < nums.length; i++) {
            // i != start这个可大有讲究，以【1,2,2】为例，
            // 它保证了可以收集到【1,2，2】【2,2】等结果
            // 不能写成 i != 0，这样会漏掉很多
            // 剪枝减的主要是在每次准备在剩余集合里挑元素时，已经挑过一遍的情况
            if (i != start && nums[i] == nums[i - 1]) {
                continue;
            }
            path.add(nums[i]);
            backtrack(nums, i + 1);
            path.remove(path.size() - 1);
        }
    }
}