题目描述
给你一个整数数组nums，数组中的元素互不相同。返回该数组所有可能的子集（幂集）。
解集不能包含重复的子集。你可以按任意顺序返回解集。
示例
示例 1： 输入：nums = [1,2,3] 输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]] 示例 2： 输入：nums = [0] 输出：[[],[0]]提示：
- 1 <= nums.length <= 10
- -10 <= nums[i] <= 10
- nums 中的所有元素互不相同
解题思路总览
| 方法 | 核心思想 | 时间复杂度 | 空间复杂度 | 备注 |
|---|---|---|---|---|
| 回溯（DFS） | 深度优先搜索枚举所有子集 | O(2^n * n) | O(n) | 推荐解法 |
| 迭代（位运算） | 用二进制位表示子集 | O(2^n * n) | O(1) | 经典方法 |
| 递归 | 数学归纳思想 | O(2^n * n) | O(n) | 另一种思路 |
一、核心解法：回溯（DFS）
核心思想
回溯算法：从空集开始，逐步添加元素，枚举所有可能的子集。
关键洞察： 1. 子集问题的本质： - 每个元素都有两个选择：选或不选 - 共 2^n 种子集 - 与排列不同，子集不关心元素的顺序 2. 状态表示： - path: 当前已选择的元素（子集） - index: 当前处理到第几个元素 - 从 index 开始选择后面的元素 3. 回溯思想： - 每个位置有两种选择：选 nums[i] 或不选 - 通过控制 index 实现"选或不选"的选择图解
nums = [1, 2, 3] 决策树： [] / | \ [] [1] [2] [3] / | / | / | / | [] [1] [1] [1,2] [2] [2,3] [3] [1,3] ... ... ... ... ... ... ... ... 完整决策树： 从 [] 开始： index=0: 选择或不选择 1 ├── 不选 1: index=1 │ ├── 不选 2: index=2 │ │ ├── 不选 3: 输出 [] │ │ └── 选 3: 输出 [3] │ └── 选 2: index=2 │ ├── 不选 3: 输出 [2] │ └── 选 3: 输出 [2,3] └── 选 1: index=1 ├── 不选 2: index=2 │ ├── 不选 3: 输出 [1] │ └── 选 3: 输出 [1,3] └── 选 2: index=2 ├── 不选 3: 输出 [1,2] └── 选 3: 输出 [1,2,3] 所有子集: [], [1], [2], [3], [1,2], [1,3], [2,3], [1,2,3]二、算法流程图
输入: nums = [1, 2, 3] 初始化: ans = [] path = [] 递归 DFS(index=0): ans.push_back([]) // 空集 遍历 i = 0, 1, 2: i=0: path.push_back(1) -> path=[1] DFS(index=1) ans.push_back([1]) 遍历 i=1,2: i=1: path.push_back(2) -> path=[1,2] DFS(index=2) ans.push_back([1,2]) 遍历 i=2: i=2: path.push_back(3) -> path=[1,2,3] DFS(index=3) ans.push_back([1,2,3]) path.pop_back() -> path=[1,2] 回溯 回溯 path.pop_back() -> path=[1] 回溯 回溯 path.pop_back() -> path=[] 回溯 ... 继续 i=1, i=2 输出: [[], [1], [1,2], [1,2,3], [1,3], [2], [2,3], [3]]三、完整代码实现
classSolution{public:vector<vector<int>>subsets(vector<int>&nums){vector<vector<int>>ans;vector<int>path;// 回溯函数function<void(int)>dfs=[&](thisauto&&self,intindex){// 每一层都记录当前的子集ans.push_back(path);// 从 index 开始，尝试选择或不选择每个元素for(inti=index;i<nums.size();i++){// 选择 nums[i]path.push_back(nums[i]);// 递归处理下一个元素（从 i+1 开始）self(i+1);// 回溯：撤销选择path.pop_back();}};// 开始回溯，从索引 0 开始dfs(0);returnans;}};四、逐行解析
vector<vector<int>>ans;vector<int>path;ans：存储所有子集path：当前正在构建的子集
ans.push_back(path);- 每一层递归都将当前 path（子集）加入 ans
- 这保证了空集和所有中间子集都被记录
for(inti=index;i<nums.size();i++){- 从 index 开始遍历
index控制我们只能选择当前及之后的元素- 这样可以避免重复（比如 [1,2] 和 [2,1]）
path.push_back(nums[i]);self(i+1);path.pop_back();- 选择 nums[i]，递归处理下一个
- 回溯时撤销选择，尝试其他可能
五、与全排列的对比
| 维度 | 第 78 题 子集 | 第 46 题 全排列 |
|---|---|---|
| 问题本质 | 每个元素选或不选 | 排列所有元素 |
| 结果数量 | 2^n 种子集 | n! 种排列 |
| 选择方式 | 线性选择（index 控制） | 环形选择（used 数组） |
| 去重需求 | 不需要（元素互不相同） | 不需要 |
| 时间复杂度 | O(2^n * n) | O(n! * n) |
子集 vs 排列： 子集 [1,2,3]： - 不关心顺序，{1,2} 和 {2,1} 是同一个子集 - 每个元素选或不选，2^n 种 排列 [1,2,3]： - 关心顺序，{1,2} 和 {2,1} 是不同排列 - 每个位置选一个未使用的元素，n! 种六、位运算解法
位运算思想：用二进制位表示子集 nums = [1, 2, 3] 二进制表示： 000 -> [] (都不选) 001 -> [3] (选第3个) 010 -> [2] (选第2个) 011 -> [2,3] (选第2、3个) 100 -> [1] (选第1个) 101 -> [1,3] (选第1、3个) 110 -> [1,2] (选第1、2个) 111 -> [1,2,3] (选全部) 代码实现： for (int mask = 0; mask < (1 << n); mask++) { vector<int> path; for (int i = 0; i < n; i++) { if (mask & (1 << i)) { path.push_back(nums[i]); } } ans.push_back(path); }七、复杂度分析
| 方法 | 时间复杂度 | 空间复杂度 | 备注 |
|---|---|---|---|
| 回溯 | O(2^n * n) | O(n) | 推荐 |
| 位运算 | O(2^n * n) | O(1) | 经典方法 |
| 递归 | O(2^n * n) | O(n) | 数学归纳 |
详细分析：
时间复杂度： 共 2^n 种子集 每种子集需要 O(n) 复制到 ans 总计：O(2^n * n) 空间复杂度： 递归深度：O(n) path：O(n) 总计：O(n)八、边界情况分析
| 情况 | 处理方式 |
|---|---|
| n = 0 | 返回 [[]]（空集的子集只有空集本身） |
| n = 1 | 返回 [[], [nums[0]]] |
| 全部正数 | 正常处理 |
| 有负数 | 正常处理，负数不影响子集生成 |
示例：n = 1
nums = [5] 回溯过程： path = [] DFS(0): ans.push_back([]) // 空集 遍历 i=0: path.push_back(5) -> path=[5] DFS(1): ans.push_back([5]) // 只有5的子集 path.pop_back() -> path=[] 输出: [[], [5]]九、面试追问 FAQ
| 问题 | 回答要点 |
|---|---|
| Q: 子集问题的核心是什么？ | 每个元素都有选或不选两种情况，共 2^n 种 |
| Q: 为什么每个递归都要 push path？ | 因为 path 的每个状态都是一个子集，包括空集 |
| Q: 为什么 index 是 i+1 而不是 index+1？ | 保证不回头选择已经跳过的元素，避免重复子集 |
| Q: 时间复杂度为什么是 O(2^n * n)？ | 2^n 种子集，每种需要 O(n) 复制 |
| Q: 空间复杂度是多少？ | O(n)（递归深度 + path） |
| Q: 如何处理有重复数字的子集？ | 需要排序 + 跳过相同元素（参考第 90 题） |
十、相关题目
| 题目编号 | 题目名称 | 难度 | 核心差异 |
|---|---|---|---|
| 78 | 子集 | 中等 | 基础题，无重复数字 |
| 90 | 子集 II | 中等 | 有重复数字，需要去重 |
| 46 | 全排列 | 中等 | 排列问题 |
| 77 | 组合 | 中等 | 组合问题 |
| 131 | 分割回文串 | 中等 | 子集变形 |
| 416 | 分割等和子集 | 困难 | 子集 + 背包 |
十一、总结
| 要点 | 内容 |
|---|---|
| 核心思想 | 回溯/位运算，枚举每个元素选或不选 |
| 关键点 | 每一层都记录当前子集到 ans |
| 遍历方式 | 从 index 开始，避免重复子集 |
| 时间复杂度 | O(2^n * n) |
| 空间复杂度 | O(n) |
| 变形 | 位运算：用二进制位表示子集 |
子集问题是经典的回溯/枚举问题，核心思想是每个元素都有选或不选两种情况，共 2^n 种子集。通过回溯或位运算可以高效枚举所有子集。
