LeetCode刷题日记之回溯算法（三）

前言

今天是学习回溯算法的第三天，我们继续来一起学习回溯算法蕴含的逻辑处理，希望博主记录的内容能够对大家有所帮助 ，一起加油吧朋友们！💪💪💪

复原IP地址

LeetCode题目链接

这道题就是给一个字符串，让我们通过插入三个.来使得其成为一个ip地址，然后判断ip地址的有效性，组成ip地址的四个整数需要为0~255之间

我们来思路梳理

• 通过递归在不同位置插入 .，将字符串划分为四个部分🤔 在插入 . 后，判断每部分是否是有效的 IP 地址段（数值在 0-255 之间，且没有前导 0）🤔 当字符串分割成四部分并且已经遍历完整个字符串时，检查其是否符合 IP 地址格式。如果符合，则将其加入结果集🤔 如果某个部分无效，或剩余的字符无法分成合法的 IP 地址部分，提前终止当前路径的递归，减少不必要的计算🤔

我们来进一步梳理回溯三要数

• 确定递归的参数和返回值

//s: 输入的字符串
//startIndex: 当前划分 IP 段的起始位置
//path: 当前已经划分出的 IP 段
//不需要返回值因为结果被直接存到结果集result中
List<String> result = new ArrayList<>();
private void backtracking(String s, int startIndex, List<String> path){}

• 回溯终止条件( 当 path 中已经有 4 段 IP 地址并且 startIndex 达到了字符串末尾，说明我们找到了一组有效的 IP 地址，加入到结果集中🤔)

// 终止条件：path 已经有 4 段 IP 且正好用完字符串
if (path.size() == 4) {
    if (startIndex == s.length()) {
        // 形成合法 IP，加入结果集
        result.add(String.join(".", path));
    }
    return;  // 否则返回，不再继续处理
}

• 单层搜索过程（ 每次从 startIndex 开始，逐步向后递增，每次截取一段子串，判断这段子串是否是合法的 IP 地址段（0-255 且不能有前导 0）🤔 如果子串合法，则递归继续处理剩下的部分，直到找到所有有效的划分方式 ）

//单层搜索过程，从 startIndex 开始，尝试截取 1 到 3 个字符组成 IP 地址段
        for(int i = startIndex; i < s.length() && i < startIndex + 3; i++){
            String segment = s.substring(startIndex, i + 1);

            //判断当前子串是否合法的ip段
            if(isValidSegment(segment)){
                path.add(segment);
                backtracking(s, i + 1, path);
                path.removeLast();//回溯
            }
        }

回溯的完整代码如下：

class Solution {
    List<String> result = new ArrayList<>();
    public List<String> restoreIpAddresses(String s) {
        //如果字符串长度过长或过短，不可能形成合法 IP，直接返回空结果
        if(s.length() < 4 || s.length() > 12){
            return result;
        }
        backtracking(s, 0, new ArrayList<>());
        return result;
    }

    private void backtracking(String s, int startIndex, List<String> path){
        // 终止条件：path 已经有 4 段 IP 且正好用完字符串
        if(path.size() == 4){
            if(startIndex == s.length()){
                result.add(String.join(".", path));
            }
            return;
        }
        

        //单层搜索过程，从 startIndex 开始，尝试截取 1 到 3 个字符组成 IP 地址段
        for(int i = startIndex; i < s.length() && i < startIndex + 3; i++){
            String segment = s.substring(startIndex, i + 1);

            //判断当前子串是否合法的ip段
            if(isValidSegment(segment)){
                path.add(segment);
                backtracking(s, i + 1, path);
                path.removeLast();//回溯
            }
        }
    }

    // 判断一个字符串是否是合法的 IP 地址段
    private boolean isValidSegment(String segment){
        // 如果以 '0' 开头且长度大于 1，则是无效的，因为不能有前导 0
        if(segment.length() > 1 && segment.charAt(0) == '0'){
            return false;
        }
        //将字符串转为整数，检查是否在合法范围内
        int num = Integer.parseInt(segment);
        return num >= 0 && num <= 255;
    }
}

子集

LeetCode题目链接

这道题就是给一个整数数组返回它所有的子集

我们来思路梳理

• 使用递归，从数组的第一个元素开始，每次决定是否将当前元素加入当前子集🤔 对于每一个元素，我们有两种选择：加入当前子集或不加入。通过这两种选择递归下去，能够生成所有的子集组合🤔 当遍历完整个数组时，将当前生成的子集加入到结果集中🤔 由于题目要求元素互不相同，因此不存在重复子集的问题，不需要去重

我们来进一步梳理回溯三要素

• 确定递归函数的参数和返回值

//nums: 输入的数组
//startIndex: 当前递归到数组的哪个位置
//path: 当前构建的子集
//result: 存储所有可能的子集的列表
List<List<Integer>> result = new ArrayList<>();
private void backtracking(int[] nums, int startIndex, List<Integer> path) {}

• 回溯终止条件

//在这个问题中，不需要显式的终止条件，因为我们每次都将当前路径（子集）加入结果集，递归自然会结束，直到遍历完整个数组🤔🤔🤔
result.add(new ArrayList<>(path));//每次递归都将当前路径（子集）加入结果集

• 单层搜索过程

for (int i = startIndex; i < nums.length; i++) {
    path.add(nums[i]);// 选择当前数字加入子集
    backtracking(nums, i + 1, path);// 递归，继续选择下一个数字（从 i+1 开始）
    path.remove(path.size() - 1);   // 回溯，移除当前数字，尝试其他组合
}

完整的回溯代码如下

class Solution {
    List<List<Integer>> result = new ArrayList<>();
    public List<List<Integer>> subsets(int[] nums) {
        backtracking(nums, 0, new ArrayList<>());
        return result;
    }

    private void backtracking(int[] nums, int startIndex, List<Integer> path){
        result.add(new ArrayList<>(path));

        for(int i = startIndex; i < nums.length; i++){
            path.add(nums[i]);
            backtracking(nums, i + 1, path);
            path.removeLast();
        }
    }
}

子集II

LeetCode题目链接

这道题相较于上题而言，改变的是所给的整数数组的数可能有重复

我们来思路梳理

• 这个问题与之前的子集问题类似，但区别在于数组中可能包含重复元素，因此在生成子集时需要避免重复子集的出现。为了解决这个问题，我们可以在递归过程中跳过重复元素，从而确保每个子集只会出现一次🤔🤔🤔所以我们先对数组进行排序，这样相同的元素会相邻出现，便于后续处理重复项🤔 使用递归生成子集，在每层递归中，对于重复的元素，跳过相同的元素🤔在同一层递归中，如果当前元素和前一个元素相同，则跳过该元素，这样可以避免重复组合的生成🤔当遍历完整个数组时，将当前的子集加入结果集

我们来进行回溯三要素梳理

• 确定递归函数的参数和返回值

//nums: 输入的整数数组（可能包含重复元素🤔）
//startIndex: 当前递归处理到的数组起始位置
//path: 当前构造中的子集
//result: 存储所有可能的子集的列表
//递归函数不需要返回值，结果将直接存入 result 列表中
List<List<Integer>> result = new ArrayList<>();
private void backtracking(int[] nums, int startIndex, List<Integer> path) {}

• 回溯终止条件（ 在这个问题中，没有显式的终止条件。每次递归都会将当前路径（子集）加入结果集，递归会自然结束，当 startIndex 达到数组末尾时不再继续🤔）

result.add(new ArrayList<>(path));//每次递归都将当前路径（子集）加入结果集

• 单层搜索过程

//单层搜索过程：从 startIndex 开始，遍历数组
for (int i = startIndex; i < nums.length; i++) {
    //去重
    if (i > startIndex && nums[i] == nums[i - 1]) continue; // 跳过重复的元素
    path.add(nums[i]);
    backtracking(nums, i + 1, path); //注意 i + 1 是因为不能重复选择当前元素
    path.remove(path.size() - 1);//回溯
}

回溯的完整代码如下

class Solution {
    List<List<Integer>> result = new ArrayList<>();
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        Arrays.sort(nums);//首先对数组进行排序，这样相同的元素会相邻，方便后续去重处理
        backtracking(nums, 0, new ArrayList<>());
        return result;
    }
    private void backtracking(int[] nums, int startIndex, List<Integer> path){
        result.add(new ArrayList<>(path));

        for(int i = startIndex; i < nums.length; i++){
            if(i > startIndex && nums[i] == nums[i - 1]) continue;
            path.add(nums[i]);
            backtracking(nums, i + 1, path);
            path.removeLast();
        }
    }
}

总结

今天的回溯就学到这里啦，这几道题的处理都是和前几天的处理逻辑大差不差，去重是一样的排序逻辑，后续博主也将会开个项目专栏分享项目学习的经验，大家一起加油，奥利给✊✊✊