LeetCode 面试题 08.04. 幂集
目录
题目描述
题意分析
给定一个元素互不相同的整数集合，返回它的所有子集，也就是幂集。每个元素在一个子集中只能出现一次，子集内部顺序和所有子集的输出顺序都没有要求。
对每个元素只有两个互斥选择：不放入当前子集，或放入当前子集。
n个元素的选择彼此独立，因此必然有 $2^n$ 个叶子，也必然产生 $2^n$ 个不同子集。空集必须包含在答案里。输入为空时并不是“没有答案”，而是只有一个子集
[[]]；这正好对应“零个元素的所有选择只有一种”。
解法：按元素做选与不选的回溯
核心思路
把搜索状态定义为
dfs(u, path)：下标[0, u)的元素已经做完决定，path恰好保存其中被选中的元素；[u, n)还未处理。到达每一层时，先走“不选nums[u]”分支，再走“选择nums[u]”分支。这是一个深度为
n的完整二叉决策树。每条根到叶路径唯一对应一个 0/1 选择向量，也就唯一对应一个子集；反过来，每个子集都能确定一条选择路径，因此既不重复也不遗漏。
path是复用的可变容器。选择分支返回后必须撤销最后加入的元素；保存答案时则必须复制path，否则所有答案会共同引用同一个容器，后续回溯会把已经保存的结果一起改掉。
解题步骤
- 从
dfs(0, emptyPath)开始，表示还没有处理任何元素。- 若
u == nums.length，当前路径已经对每个元素作出决定，复制后加入答案。- 先递归
dfs(u + 1, path)，表示不选nums[u]。- 再把
nums[u]加入路径，递归选择分支；返回后删除路径末尾，恢复进入本层前的状态。以
nums = [1,2]为例：根先不选 1，再不选 2，得到[]；返回后选 2，得到[2]；回到根选 1，再分别不选、选择 2，得到[1]、[1,2]。四条叶路径正好覆盖 $2^2$ 个子集。
代码实现
// u 之前的元素已决定，t 保存其中被选中的元素。
class Solution {
private List<List<Integer>> answer = new ArrayList<>();
private int[] nums;
public List<List<Integer>> subsets(int[] nums) {
this.nums = nums;
dfs(0, new ArrayList<>());
return answer;
}
private void dfs(int u, List<Integer> t) {
if (u == nums.length) {
answer.add(new ArrayList<>(t));
return;
}
dfs(u + 1, t);
t.add(nums[u]);
dfs(u + 1, t);
t.remove(t.size() - 1);
}
}
// u 之前的元素已决定，t 保存其中被选中的元素。
func subsets(nums []int) [][]int {
var answer [][]int
var dfs func(u int, t []int)
dfs = func(u int, t []int) {
if u == len(nums) {
answer = append(answer, append([]int(nil), t...))
return
}
dfs(u+1, t)
t = append(t, nums[u])
dfs(u+1, t)
t = t[:len(t)-1]
}
var t []int
dfs(0, t)
return answer
}
复杂度分析
- 时间复杂度：$O(n \cdot 2^n)$。共有 $2^n$ 个子集，复制一个子集最坏需要 $O(n)$；所有输出元素总数实际为 $n \cdot 2^{n-1}$。
- 空间复杂度：不计返回结果时为 $O(n)$，来自递归栈与当前路径；结果本身占 $O(n \cdot 2^n)$。
关键点总结
- 子集题的标准状态是“处理到哪个位置 + 当前选择”，每个元素恰好产生选 / 不选两个分支。
- 叶子收集与沿途收集都能写；本实现只在所有元素决定完后收集，不变量最直接。
- 面试官若追问位运算，可以枚举
mask = 0..(1<<n)-1，第i位为 1 就选择nums[i]，复杂度相同。- 若输入允许重复元素，就不能直接套本题；需要先排序并做同层去重，对应 90 题。
易错点总结
- 叶子处直接保存可变路径引用：
nums = [1]时，回溯撤销后先前保存的[1]也会变成[]；必须复制。- 选择分支返回后忘记撤销：
nums = [1,2]的后续兄弟分支会携带本不该存在的元素，出现重复或非法子集。- 把空输入返回成空列表：
nums = []的幂集应是[[]]，不是[]。- 误以为时间复杂度只有 $O(2^n)$：输出每个子集需要复制其元素，完整输出代价是 $O(n2^n)$。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 78. 子集 | 中等 | 子集回溯 |
| 90. 子集 II | 中等 | 子集回溯 |
| LCR 079. 子集 | 中等 | 子集回溯 |