🔥Flumina Blog

主题

00:00:00
🔥Flumina2025-04-22 22:04:002026-08-12 01:14:54算法笔记算法笔记C++Algorithm
1157
4.6m
0

文章发布较早，内容可能过时，阅读注意甄别。

回溯算法小记 ​

求解数组的所有子集是一个经典的回溯问题，常见的解法有两种：基于“横向遍历”的写法和基于“选与不选”的写法。下面我们将对这两种写法进行详细分析，并比较它们的异同。

🔍 代码逻辑分析 ​

代码片段 1：基于“横向遍历”的写法 ​

这种写法通常出现在“回溯算法模板”中，强调在每一层递归中通过 for 循环去尝试选择列表中的元素。

cpp
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param S int整型vector
     * @return int整型vector<vector<>>
     */
    vector<int>path;
    vector<vector<int>>result;
    static bool cmp(const vector<int>& a, const vector<int>& b) {
        if (a.size() == b.size()) {
            return a < b;
        } else {
            return a.size() < b.size();
        }
    }
    void backtracking(vector<int>& S, int startIndex) {
        result.emplace_back(path);
        if (startIndex == S.size()) {
            return;
        }
        for (int i = startIndex; i < S.size(); i++) {
            path.emplace_back(S[i]);
            backtracking(S, i + 1);
            path.pop_back();
        }
    }
    vector<vector<int> > subsets(vector<int>& S) {
        // write code here
        backtracking(S, 0);
        sort(result.begin(), result.end(), cmp);
        return result;
    }
};
  • 核心思想：这棵树是一个多叉树。在每一层，我们决定“下一个元素选谁”。
  • 特点：result.emplace_back(path) 放在递归终止条件之前。这意味着，只要进入这一层，当前的 path 就是一个合法的子集（无论是空集还是部分集），都会被记录。

代码片段 2：基于“选与不选”的写法 ​

这种写法更贴近二叉树的逻辑，对于数组中的每一个元素，我们只有两个选择：要它，或者不要它。

cpp
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param S int整型vector
     * @return int整型vector<vector<>>
     */
    vector<int>path;
    vector<vector<int>>result;
    static bool cmp(const vector<int>& a, const vector<int>& b) {
        if (a.size() == b.size()) {
            return a < b;
        } else {
            return a.size() < b.size();
        }
    }
    void backtracking(vector<int>& S, int startIndex) {
        if (startIndex == S.size()) {
            result.emplace_back(path);
            return;
        }
        // 不选当前元素
        backtracking(S, startIndex + 1);

        // 选当前元素
        path.push_back(S[startIndex]);
        backtracking(S, startIndex + 1);
        path.pop_back(); // 回溯
    }
    vector<vector<int> > subsets(vector<int>& S) {
        // write code here
        backtracking(S, 0);
        sort(result.begin(), result.end(), cmp);
        return result;
    }
};
  • 核心思想：这棵树是一个二叉树（高度为 N）。左分支代表“不选”，右分支代表“选”。
  • 特点：result.emplace_back(path) 放在终止条件里。只有当我们对数组中所有元素都做出了“选”或“不选”的决定（即到达叶子节点）时，才记录结果。

📊 对比分析 ​

功能等价性 ​

假设输入数组 S=[1,2]：

  • 代码 1 的执行流：

    1. 初始调用，path=[]，加入结果。循环选 1。
    2. 递归，path=[1]，加入结果。循环选 2。
    3. 递归，path=[1, 2]，加入结果。
    4. 回溯... 最终结果集包含：[], [1], [1, 2], [2]。

  • 代码 2 的执行流：

    1. 针对 1：先走“不选”分支，再走“选”分支。
    2. 针对 2：在上面的基础上，分别再走“不选”和“选”。
    3. 到达叶子节点记录。最终结果集包含：[], [2], [1], [1, 2]。

结论：两者生成的子集内容完全一致，只是生成的顺序可能略有不同（取决于具体的遍历顺序），但作为集合的集合，它们是相等的。

复杂度分析 ​

  • 时间复杂度：两者都是 O(N×2N)。
    • 都需要遍历 2N 种状态。
    • 每次构造子集（拷贝 path 到 result）需要 O(N) 的时间。
  • 空间复杂度：两者都是 O(N)。
    • 递归栈的深度最大为 N。
    • path 变量占用的空间最大为 N。

适用场景差异 ​

  • 代码 1 (for 循环版)：
    • 通用性强：这是解决组合、切割、子集问题的标准模板。
    • 易于扩展：如果题目变成“求所有长度为 K 的子集”，只需要在函数开头加一个 if (path.size() == K) 的判断即可，或者修改 for 循环的边界。
  • 代码 2 (选/不选版)：
    • 逻辑直观：对于“0/1 背包问题”或者简单的“每个物品选不选”的问题，这种逻辑非常清晰。
    • 局限性：如果问题变成“每个元素可以选多次”或者“从 N 个数中选 K 个”，这种写法的修改不如代码 1 方便。

📌 总结 ​

这两段代码功能一样，都是求数组的所有子集。

  • 如果你在做回溯算法的通用练习（如 LeetCode 78. 子集），代码 1 是更标准的写法，因为它符合回溯算法“遍历决策树”的通用模型。
  • 如果你在处理特定逻辑（如每个位置只有两种状态），代码 2 的可读性可能更高。
最近更新