用递归算法解锁「子集」问题 —— LeetCode 78题解析

递归算法是编程中一种非常强大且常见的思想，它能够优雅地解决很多复杂的问题，比如树的遍历、组合问题、回溯搜索等。

今天，我们以 LeetCode 第 78 题「子集（Subsets）」为例，带大家深入理解递归的思路、实现细节以及不同写法的差异。

一、题目介绍

题目链接： 78. 子集 - LeetCode

题目描述：
给定一个整数数组 nums，返回该数组所有可能的子集（幂集）。

示例：

输入: nums = [1,2,3]
输出: [[], [1], [2], [3], [1,2], [1,3], [2,3], [1,2,3]]

二、递归思路详解：从决策树开始理解

我们用递归的方式去“做决策”——对每个元素，都面临两个选择：

• 选择它
• 不选择它

这种决策结构，其实就像是一棵二叉树：
每一个节点都有两个分支，一个是“我选了当前元素”，另一个是“我跳过当前元素”。

举例说明

以 nums = [1, 2] 为例，整个决策过程如下所示：

                []/    \[1]     []/   \      \[1,2]   [1]     [2]

每一条路径就是一个子集的构建过程：

• []：什么都不选
• [1]：只选第一个
• [1,2]：全选
• [2]：只选第二个

最终收集所有路径，就是所有的子集

用语言描述递归过程：

• 从位置 0 开始：
  • 选 nums[0]，进入下一层递归
  • 选 nums[1]，递归到尽头，保存 [1,2]
  • 不选 nums[1]，保存 [1]
• 不选 nums[0]
  • 选 nums[1]，保存 [2]
  • 不选 nums[1]，保存 []

这样，我们就得到了所有子集。

三、解法一：二叉决策树 DFS

解法思路
每次递归考虑一个元素，选或不选。
当走到数组末尾时，当前构建的路径就是一个合法的子集。

class Solution 
{vector<vector<int>> ret;  // 存放结果集vector<int> path;         // 当前构建的子集路径
public:vector<vector<int>> subsets(vector<int>& nums) {dfs(nums, 0);         // 从索引 0 开始递归return ret;}void dfs(vector<int>& nums, int pos){if (pos == nums.size()) // 递归出口：遍历完所有元素{ret.push_back(path); // 加入当前路径return;}// 选择当前元素path.push_back(nums[pos]);dfs(nums, pos + 1);path.pop_back(); // 回溯，撤销选择// 不选择当前元素dfs(nums, pos + 1);}
};

四、解法二：组合式回溯写法（推荐）

思路核心
我们从当前下标 pos 开始向后遍历，每次选一个元素加入 path，递归处理后续子集，不再考虑当前之前的元素，避免重复。

这种方式更像是“组合问题”的模板写法。

决策过程

• 每进入递归一次，就把当前 path 加入结果集
• 然后，从当前位置 pos 开始遍历，尝试将每个元素加入 path，并递归后续
• 回溯：递归返回后，需要把最后加入的元素移除，恢复现场

举例说明：

                           []┌───────────────┼────────────────┐[1]              [2]             [3]/     \          /     \             \[1,2]   [1,3]     [2,3]                  [3]|        |         |[1,2,3]  [1,3]     [2,3]

用语言描述过程：
从 pos = 0 开始：

1. 先将空集 [] 加入结果集。
2. 遍历索引 0~2：
   • 选择 nums[0]=1，路径变为 [1]
     • 继续从 pos=1 开始遍历：
       • 选 2 -> [1,2]
         • 选 3 -> [1,2,3]
       • 回溯到 [1]
       • 选 3 -> [1,3]
   • 回溯回到 []
   • 选 2 -> [2]
     • 选 3 -> [2,3]
   • 回溯回到 []
     • 选 3 -> [3]
       每一步都把当前的路径保存下来，形成最终的子集集合。

代码实现

class Solution 
{vector<vector<int>> ret;vector<int> path;
public:vector<vector<int>> subsets(vector<int>& nums) {dfs(nums, 0); // 从第 0 个元素开始扩展return ret;}void dfs(vector<int>& nums, int pos){ret.push_back(path); // 每个路径都是一个合法子集for (int i = pos; i < nums.size(); i++){path.push_back(nums[i]);dfs(nums, i + 1);   // 继续递归下一个元素path.pop_back();    // 回溯，移除当前元素}}
};

优点分析

• 不需要写递归出口，利用 for 循环自动控制终止条件
• 结构上类似「组合问题」的回溯模板

为什么说它更像‘组合问题’？
因为组合问题也遵循一个核心原则：

• 每次只能向后选元素，不能回头，以防止重复。

比如要从 [1,2,3] 中选出长度为 2 的组合，这种“向后递归 + 回溯”的结构是最自然的选择。

五、解法对比

比较维度	解法一（选/不选）	解法二（组合式回溯）
决策方式	二分支：选 or 不选	枚举所有起点及其后续路径
是否需要出口判断	是（pos == nums.size()）	否，for 控制终止
可读性	模拟决策树，结构清晰	更接近组合枚举的写法
常见用途	子集、排列、二叉树类问题	子集、组合、N 皇后等问题