代码随想录算法训练营 Day21 | 回溯算法 part03

2401_86818319

466人浏览 · 2026-03-27 09:42:18

2401_86818319 · 2026-03-27 09:42:18 发布

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 {
public:
    vector<string> ans;
    // 辅助函数：检查子串是否合法
    bool check(string s) {
        if (s.size() <= 0 || s.size() > 3) return false;       // 长度限制
        if (s[0] == '0' && s.size() > 1) return false;         // 前导零限制
        int sum = 0;
        for (char c : s) {
            if (!isdigit(c)) return false;                     // 非法字符检查
            sum = sum * 10 + (c - '0');
            if (sum > 255) return false;                       // 数值大小限制
        }
        return true;
    }
    // 回溯函数
    // s: 原字符串
    // path: 当前构建的IP地址前缀（引用传递，需手动回溯）
    // cnt: 已经添加的点的数量（0到3）
    // startIndex: 当前处理的原字符串起始位置
    void backtracking(string s, string& path, int cnt, int startIndex) {
        // 1. 终止条件：已经加了3个点
        if (cnt == 3) {
            string tmp = s.substr(startIndex); // 获取剩余部分作为最后一段
            if (check(tmp)) {
                ans.push_back(path + tmp);     // 拼接最后一段并加入结果
            }
            return;
        }
        // 2. 单层搜索逻辑
        for (int i = startIndex; i < s.size(); i++) {
            string tmp = s.substr(startIndex, i - startIndex + 1); // 截取子串
            if (check(tmp)) {
                // 处理节点：拼接子串和点
                path += tmp + "."; 
                backtracking(s, path, cnt + 1, i + 1); // 递归：点数+1，位置后移
                // 回溯：撤销处理
                // 删除刚才添加的子串和点，长度为 tmp.size() + 1
                path.erase(path.size() - (tmp.size() + 1)); 
            } else {
                break; // 剪枝：如果当前子串不合法，更长的子串也不合法，直接break
            }
        }
    }
    vector<string> restoreIPAddresses(string s) {
        string path;
        ans.clear();
        // 剪枝：IP地址长度只能在4到12之间
        if (s.size() < 4 || s.size() > 12) return ans;
        backtracking(s, path, 0, 0);
        return ans;
    }
};

// 值传递 + 自动回溯
class Solution {
public:
    vector<string> ans;
    // 检查函数同上
    bool check(string s) {
        if (s.size() <= 0 || s.size() > 3) return false;
        if (s[0] == '0' && s.size() > 1) return false;
        int sum = 0;
        for (char c : s) {
            if (!isdigit(c)) return false;
            sum = sum * 10 + (c - '0');
            if (sum > 255) return false;
        }
        return true;
    }
    // path 使用值传递（不带 &）
    void backtracking(string s, string path, int cnt, int startIndex) {
        if (cnt == 3) {
            string tmp = s.substr(startIndex);
            if (check(tmp)) {
                ans.push_back(path + tmp);
            }
            return;
        }
        for (int i = startIndex; i < s.size(); i++) {
            string tmp = s.substr(startIndex, i - startIndex + 1);
            if (check(tmp)) {
                // 关键区别：直接在递归调用时修改参数
                // path + tmp + "." 会生成一个新的临时 string 对象传给下一层
                // 下一层的修改不会影响当前层的 path
                backtracking(s, path + tmp + ".", cnt + 1, i + 1);
                // 不需要 pop_back 或 erase！
            } else {
                break; 
            }
        }
    }
    vector<string> restoreIPAddresses(string s) {
        string path;
        ans.clear();
        if (s.size() < 4 || s.size() > 12) return ans;
        backtracking(s, path, 0, 0);
        return ans;
    }
};

总结

1. 核心区别：状态管理

特性	版本一 (引用传递 `string& path`)	版本二 (值传递 `string path`)
内存模型	全局唯一。所有递归层级共享同一个 `path` 对象。	层级独立。每一层递归都持有 `path` 的一个副本。
回溯操作	显式回溯。必须手动执行 `erase` 撤销修改，恢复到上一层状态。	隐式回溯。函数结束返回时，局部变量 `path` 自动销毁，上一层 `path` 未被修改。
性能开销	较低。没有字符串拷贝开销，只有引用传递。	较高。每次递归都要复制一次 `path` 字符串。
代码复杂度	稍高。需要仔细计算 `erase`的长度，容易出错。	极低。代码线性，不需要考虑撤销逻辑，非常直观。

2. 易错点分析

版本一易错点：
- path.erase(path.size() - (tmp.size() + 1)); 这里必须精确计算删除的长度（子串长度+一个点）。如果计算错误，会导致 path 内容错乱。
版本二易错点：
- 不要滥用。如果题目数据量变大（例如子集问题，数组长度 1000），每次递归都复制 vector 或 string 会导致严重的超时或内存溢出。

78. 子集

给你一个整数数组 nums ，数组中的元素互不相同。返回该数组所有可能的子集（幂集）。

解集不能包含重复的子集。你可以按任意顺序返回解集。

class Solution {
public:
    vector<int> path;           // 当前子集路径
    vector<vector<int>> ans;    // 结果集，存储所有子集
    // 回溯函数
    // nums: 原数组
    // startIndex: 本次搜索的起始位置
    void backtracking(vector<int>& nums, int startIndex) {
        // 1. 收集结果
        // 与组合问题不同，子集问题在每一次进入递归时都要收集结果
        // 因为子集包括空集、前缀子集等，每个节点都是一个合法的子集
        ans.push_back(path);
        // 2. 单层搜索逻辑
        // 横向遍历数组
        for (int i = startIndex; i < nums.size(); i++) {
            path.push_back(nums[i]);            // 处理节点
            backtracking(nums, i + 1);          // 递归：从 i+1 开始，不重复选取当前元素
            path.pop_back();                    // 回溯：撤销处理
        }
    }
    vector<vector<int>> subsets(vector<int>& nums) {
        path.clear();
        ans.clear();
        backtracking(nums, 0);
        return ans;
    }
};

总结

1. 结果收集的时机（关键区别）

组合问题：只有当路径满足特定条件（如 path.size() == k）时，才收集结果（在树的叶子节点收集）。
子集问题：每一个节点都是一个合法的子集。
- 刚进入函数时，path 为空（收集空集）。
- 第一层递归，path 长度为 1（收集单元素子集）。
- 第二层递归，path 长度为 2（收集双元素子集）。
- 因此，代码中 ans.push_back(path) 放在函数的开头，确保所有节点都被记录。

2. 递归树结构

假设 nums = [1, 2, 3]：

第一层循环 (startIndex=0)：
- path={} -> 收集 []
- 取1 -> path={1} -> 递归
  - 第二层 (startIndex=1)：
    - 收集 [1]
    - 取2 -> path={1,2} -> 递归 -> 收集 [1,2]
    - 取3 -> path={1,3} -> 递归 -> 收集 [1,3]
- 回溯，path 变回 []
- 取2 -> path={2} -> 递归
  - …以此类推

3. 终止条件去哪了？

你会发现代码里没有显式的 if (终止条件) return;。

因为 startIndex 每次都会 +1。
当 startIndex 超过 nums.size() 时，for 循环的条件 i < nums.size()不满足，循环自动结束，函数自然结束。
所以，循环的结束就是递归的终止。

4. 复杂度分析

时间复杂度：O(N * 2^N)。
- 一个长度为 N 的集合有 2^N 个子集。
- 生成每个子集并放入结果集平均需要 O(N) 的时间。
空间复杂度：O(N)。
- 递归栈深度最大为 N。

90. 子集 II

给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。

解集不能包含重复的子集。返回的解集中，子集可以按任意顺序排列。

// used数组法
class Solution {
public:
    vector<int> path;
    vector<vector<int>> ans;
    void backtracking(vector<int>& nums, vector<bool>& used, int startIndex) {
        // 收集结果：每个节点都是一个子集
        ans.push_back(path);
        for (int i = startIndex; i < nums.size(); i++) {
            // 去重逻辑：
            // 如果当前元素和前一个相同，且前一个元素未被使用（说明是同层回溯回来的）
            // 则跳过当前元素，避免重复子集
            if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) continue;
            path.push_back(nums[i]);
            used[i] = true; // 记录使用状态
            backtracking(nums, used, i + 1);
            used[i] = false; // 回溯：恢复状态
            path.pop_back();
        }
    }
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        path.clear();
        ans.clear();
        vector<bool> used(nums.size(), false); // 辅助数组
        sort(nums.begin(), nums.end());        // 排序是去重的前提
        backtracking(nums, used, 0);
        return ans;
    }
};

// startIndex 判重法
class Solution {
public:
    vector<int> path;
    vector<vector<int>> ans;
    void backtracking(vector<int>& nums, int startIndex) {
        ans.push_back(path);
        for (int i = startIndex; i < nums.size(); i++) {
            // 去重逻辑：
            // i > startIndex: 说明当前不是本层循环的第一个元素
            // nums[i] == nums[i-1]: 说明和本层前一个元素值相同
            // 这代表本层已经处理过该值的分支了，直接跳过
            if (i > startIndex && nums[i] == nums[i - 1]) continue;
            path.push_back(nums[i]);
            backtracking(nums, i + 1);
            path.pop_back();
        }
    }
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        path.clear();
        ans.clear();
        sort(nums.begin(), nums.end()); // 排序是去重的前提
        backtracking(nums, 0);
        return ans;
    }
};

总结

1. 核心逻辑对比

特性	版本一 (`used` 数组)	版本二 (`startIndex` 判断)
判断依据	显式状态。依赖外部数组记录元素是否在当前路径中。	隐式逻辑。依赖循环索引 `i`与起始位置 `startIndex` 的关系。
判断公式	`nums[i]==nums[i-1] && !used[i-1]`	`nums[i]==nums[i-1] && i > startIndex`
原理	如果前一个相同元素被标记为 `false`，说明刚回溯回来（树层）；如果是 `true`，说明在向下递归（树枝）。	如果 `i == startIndex`，说明是本层第一个元素，允许选取；如果 `i > startIndex`，说明是本层后续元素，若值相同则重复。
空间复杂度	O(N) (需要 `used` 数组)	O(1) (除了递归栈和路径，无需额外空间)

2. 图解分析（假设 nums = [1, 2, 2]）

版本一 (used) 的视角：

第一层选取 1，used[0]=true。
第二层选取第一个 2 (index=1)，used[1]=true。递归返回后，used[1] 变回 false。
第二层循环继续，遇到第二个 2 (index=2)。
判断：nums[2] == nums[1] 且 used[1] == false。
结论：前一个 2 刚弹出去，我又来了，这是树层重复，跳过！

版本二 (startIndex) 的视角：

第一层 (startIndex=0)：选 1，递归。
第二层 (startIndex=1)：选第一个 2 (i=1)，此时 i == startIndex，合法，递归。
回溯回来，继续第二层循环，遇到第二个 2 (i=2)。
判断：nums[2] == nums[1] 且 i (2) > startIndex (1)。
结论：i 跑到了 startIndex 后面，说明本层已经处理过 2 了，这是树层重复，跳过！

3. 总结与推荐

版本一（used 数组）：
- 适用场景：排列问题（Permutation）或逻辑复杂的组合问题。
- 理由：在排列问题中，startIndex 不适用（因为排列需要从头遍历），必须依靠 used 数组来区分元素是否被选取以及去重。它是“万金油”写法。
版本二（startIndex 判断）：
- 适用场景：组合问题（Combination）和子集问题（Subsets）。
- 理由：这类问题天然具有“顺序性”（后面的元素索引一定大于前面），利用这个特性可以省去 used 数组，代码更简洁、运行效率更高。