题目描述给你一个整数数组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] 10nums 中的所有元素互不相同解题思路总览方法核心思想时间复杂度空间复杂度备注回溯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] ... ... ... ... ... ... ... ... 完整决策树 从 [] 开始 index0: 选择或不选择 1 ├── 不选 1: index1 │ ├── 不选 2: index2 │ │ ├── 不选 3: 输出 [] │ │ └── 选 3: 输出 [3] │ └── 选 2: index2 │ ├── 不选 3: 输出 [2] │ └── 选 3: 输出 [2,3] └── 选 1: index1 ├── 不选 2: index2 │ ├── 不选 3: 输出 [1] │ └── 选 3: 输出 [1,3] └── 选 2: index2 ├── 不选 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(index0): ans.push_back([]) // 空集 遍历 i 0, 1, 2: i0: path.push_back(1) - path[1] DFS(index1) ans.push_back([1]) 遍历 i1,2: i1: path.push_back(2) - path[1,2] DFS(index2) ans.push_back([1,2]) 遍历 i2: i2: path.push_back(3) - path[1,2,3] DFS(index3) ans.push_back([1,2,3]) path.pop_back() - path[1,2] 回溯 回溯 path.pop_back() - path[1] 回溯 回溯 path.pop_back() - path[] 回溯 ... 继续 i1, i2 输出: [[], [1], [1,2], [1,2,3], [1,3], [2], [2,3], [3]]三、完整代码实现classSolution{public:vectorvectorintsubsets(vectorintnums){vectorvectorintans;vectorintpath;// 回溯函数functionvoid(int)dfs[](thisautoself,intindex){// 每一层都记录当前的子集ans.push_back(path);// 从 index 开始尝试选择或不选择每个元素for(intiindex;inums.size();i){// 选择 nums[i]path.push_back(nums[i]);// 递归处理下一个元素从 i1 开始self(i1);// 回溯撤销选择path.pop_back();}};// 开始回溯从索引 0 开始dfs(0);returnans;}};四、逐行解析vectorvectorintans;vectorintpath;ans存储所有子集path当前正在构建的子集ans.push_back(path);每一层递归都将当前 path子集加入 ans这保证了空集和所有中间子集都被记录for(intiindex;inums.size();i){从 index 开始遍历index控制我们只能选择当前及之后的元素这样可以避免重复比如 [1,2] 和 [2,1]path.push_back(nums[i]);self(i1);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) { vectorint 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) pathO(n) 总计O(n)八、边界情况分析情况处理方式n 0返回 [[]]空集的子集只有空集本身n 1返回 [[], [nums[0]]]全部正数正常处理有负数正常处理负数不影响子集生成示例n 1nums [5] 回溯过程 path [] DFS(0): ans.push_back([]) // 空集 遍历 i0: 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 是 i1 而不是 index1保证不回头选择已经跳过的元素避免重复子集Q: 时间复杂度为什么是 O(2^n * n)2^n 种子集每种需要 O(n) 复制Q: 空间复杂度是多少O(n)递归深度 pathQ: 如何处理有重复数字的子集需要排序 跳过相同元素参考第 90 题十、相关题目题目编号题目名称难度核心差异78子集中等基础题无重复数字90子集 II中等有重复数字需要去重46全排列中等排列问题77组合中等组合问题131分割回文串中等子集变形416分割等和子集困难子集 背包十一、总结要点内容核心思想回溯/位运算枚举每个元素选或不选关键点每一层都记录当前子集到 ans遍历方式从 index 开始避免重复子集时间复杂度O(2^n * n)空间复杂度O(n)变形位运算用二进制位表示子集子集问题是经典的回溯/枚举问题核心思想是每个元素都有选或不选两种情况共 2^n 种子集。通过回溯或位运算可以高效枚举所有子集。