DFS 专题：子集问题深度解析与 C++ 实现

3. 解题思路

本题可以通过构建决策树来理清逻辑。我们通常有两种常见的决策路径。

3.1 决策树一：包含与不包含

从集合论基础可知，一个包含 n 个元素的集合，其子集总数为 2^n 个。这个 2^n 是怎么来的？

对于每一个元素来说，只有两种状态：存在或者不存在。对每个元素进行这种二元划分，就能得到完整的子集空间。

观察决策树可以发现，结果完全符合预期。基于此，我们需要维护两个关键变量：

• path：记录当前路径上的元素（即当前子集）。
• ret：二维数组，用于收集所有满足条件的子集结果。

递归参数设计：

• nums：原始输入数组。
• pos：当前处理到的元素索引。

逻辑流程：

1. 终止条件：当遍历到叶子节点时，将当前 path 加入 ret。
2. 分支选择：对于当前元素，分两种情况讨论——选入 path 或不选。
   • 选：加入 path，进入下一层。
   • 不选：直接跳过，进入下一层。

3.2 决策树二：按顺序选取

另一种思路是根据子集中元素的个数来构建决策图。这种方式本质上是在做组合。

由于子集内部没有顺序要求（即 [1,2] 和 [2,1] 视为同一个子集），为了避免重复，我们需要剪枝。

剪枝策略： 按照数组下标顺序添加元素。例如，如果选择了下标为 i 的元素，下一次只能从 i+1 开始选择。这样天然避免了重复组合。

值得注意的是，数组往往是多叉树的遍历，多叉树必然用到 for 循环。在这种模式下，不需要设置显式的 return 出口，因为 for 循环遍历完自然结束，本质上是'没有可选择元素'时的隐式终止。

4. C++ 代码实现

结合上述第一种决策树思路（包含/不包含），我们可以写出如下标准解法：

class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int>> ret;
        vector<int> path;
        dfs(nums, 0, path, ret);
        return ret;
    }

private:
    void dfs(const vector<int>& nums, int pos, vector<int>& path, vector<vector<int>>& ret) {
        // 每次进入函数，当前的 path 就是一个合法的子集
        ret.push_back(path);

        // 尝试添加后续元素
        for (int i = pos; i < nums.size(); i++) {
            path.push_back(nums[i]);      // 做选择
            dfs(nums, i + 1, path, ret);  // 递归
            path.pop_back();              // 撤销选择
        }
    }
};

代码解析：

• 这里采用了第二种决策树（按顺序选取）的逻辑，因为它更简洁且不易出错。
• dfs 函数的第一行就是 ret.push_back(path)，这意味着每到达一个节点，无论是否继续向下，当前的 path 都是一个有效子集。
• 循环起始位置 i = pos 保证了元素只增不减，从而避免重复。

5. 后续预告

掌握了子集问题后，可以进一步挑战变体题目：找出所有子集的异或总和再求和。这类题目通常需要在回溯过程中维护额外的状态值。