算法训练营day25 | {93.复原IP地址, 78.子集, 90.子集II}

第七章回溯算法part03，分割问题、子集问题。分割问题要注意合法终止条件的判断。

93. 复原IP地址

• 题目链接：93. 复原 IP 地址
• 文档讲解：代码随想录–93. 复原 IP 地址
• 视频讲解：回溯算法如何分割字符串并判断是合法IP？| LeetCode：93.复原IP地址
• 状态：和昨天的分割字符串大体上是一样的，但是对于终止条件我想错了，以及没有剪枝。

1.1 解题分析

• 分析回溯算法三部曲：

  1. 参数和返回值是什么？ 需要一个startIndex，记录当前切割到哪里了
  2. 确定递归的终止条件。 当遍历到字符串末尾，并且正好是4段字符串，说明找到了一个可行解，加入到result中，本层递归终止；
  3. 确定单层搜索的过程。 for循环横向遍历，负责切割字符串，并且在这里判断数字是否符合ip地址的要求，递归纵向遍历，与回溯配合使用。

• 第一遍做错的点：

  1. 终止条件不完整，IP段数没限制，IP地址必须是4段，不能少，也不能多。
  2. 前导0判断逻辑是错的，把单个’0’这种情况判定为false；
  3. 剪枝晚了，对于超过3位数的数字串，不应该切割出来；
  4. 缺少剪枝1：当IP地址段数已经超过4段时，应该终止本层递归；
  5. 缺少剪枝2：当剩余的字符数量不合理时，也没有必要继续递归，应该提前终止。

▶

93. 复原IP地址

class Solution {
    private List<String> path = new ArrayList<>();
    private List<String> result =  new ArrayList<>();

    public List<String> restoreIpAddresses(String s) {
        backtracking(s, 0);
        return result;
    }

    public void backtracking(String s, int startIndex) {
        if (path.size() > 4) return;  // 剪枝
        if(path.size() == 4) {
            if (startIndex == s.length()) result.add(String.join(".", path));
            return;
        }
        int remain = s.length() - startIndex;  // 剪枝：剩余字符数不合理
        int need = 4 - path.size();
        if (remain < need || remain > need * 3) return;
        for (int i = startIndex; i < s.length() && i < startIndex + 3; i++) {
            String sub = s.substring(startIndex, i + 1);
            if (!isSuit(sub)) continue;
            
            path.add(sub);
            backtracking(s, i + 1);
            path.remove(path.size() - 1);
        }
    }

    private boolean isSuit(String s) {
        // 前导0判断
        if (s.length() > 1 && s.charAt(0) == '0') return false;
        return Integer.parseInt(s) <= 255;
    }
}

78. 子集

• 题目链接：78.子集
• 文档讲解：代码随想录–78.子集
• 视频讲解：回溯算法解决子集问题，树上节点都是目标集和！ | LeetCode：78.子集
• 状态：不需要任何剪枝，因为是收集树形结构中，每一个节点的结果。

2.1 解题分析

子集问题，和组合问题、分割问题都抽象为一棵树的话，那么组合问题和分割问题都是收集树的叶子节点，而子集问题是找树的所有节点。子集问题也是一种组合问题，因为它的集合是无序的，子集{1,2}和子集{2,1}是一样的，因此，取过的元素不会重复取，需要startIndex控制遍历开始的位置。

▶

78. 子集

private List<Integer> path = new ArrayList<>();
    private List<List<Integer>> result =  new ArrayList<>();

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

90. 子集II

• 题目链接：90.子集II
• 文档讲解：代码随想录–90.子集II
• 视频讲解：回溯算法解决子集问题，如何去重？| LeetCode：90.子集II
• 状态：给的整数数组可能包含重复元素，要求去重。

3.1 解题分析

• 和组合问题的去重一样，要先对整数数组排序，然后定义一个used数组，同一树层的元素如果一致要进行去重。

▶

90. 子集II

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

    public List<List<Integer>> subsetsWithDup(int[] nums) {
        Arrays.sort(nums);
        backtracking(nums, 0, new boolean[nums.length]);
        return result;
    }
    
    public void backtracking(int[] nums, int startIndex, boolean[] used) {
        result.add(new ArrayList<>(path));
        
        for (int i = startIndex; i < nums.length; i++) {
            if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) continue;
            path.add(nums[i]);
            used[i] = true;
            backtracking(nums, i + 1, used);
            path.remove(path.size() - 1);
            used[i] = false;
        }
    }
}

• 但在本题中，实现同一树层的去重，实际上并不需要使用used数组，在同一层中，如果当前值和前一个值相同，跳过即可：

  if (i > startIndex && nums[i] == nums[i - 1]) continue;