LeetCode 面试题 08.04. 幂集
题目描述
题意分析
返回元素互不相同的整数集合的全部子集，包括空集。每个元素在一个子集中只可能出现一次，子集及其元素的输出顺序不影响答案。
子集只关心哪些元素被选中，不需要重新安排元素位置。因此可以固定输入顺序，对每个元素分别决定“选”或“不选”，避免把同一组元素的不同排列重复输出。
解法：按元素做选与不选的回溯
核心思路
[!blue]
定义
dfs(u, t)：下标[0, u)的元素已经决定是否选取，t保存其中选中的元素；从u开始的元素还未处理。当前元素只有两个互斥选择。不选时，路径不变，递归到
u + 1；选择时，先把nums[u]加到路径末尾，再递归到u + 1，返回后恢复本层路径。两种选择都只推进下标，不会再次处理已经决定过的元素。当
u == nums.length，所有元素都已决定，当前路径就是一个完整子集。每条从根到叶的路径对应一个唯一的选取方案；反过来，任意子集也唯一确定每个元素选还是不选。输入元素互异，因此这些叶子既不重复，也不遗漏。保存答案时必须复制当前路径。Java 的列表是可变对象，Go 的切片也可能共用底层数组，直接保留当前容器会让后续搜索影响已经保存的子集。复制只发生在叶子，搜索过程中继续复用路径。
解题步骤
- 从下标 0 和空路径开始搜索。
- 如果下标已到数组末尾，复制当前路径加入答案，并结束当前调用。
- 先递归处理“不选当前元素”的分支。
- 将当前元素追加到路径，递归处理“选择当前元素”的分支，再恢复路径长度。
- 全部递归结束后返回答案。一路不选会得到空集；输入为空时，初次调用就收集空路径，结果仍包含一个空集。
代码实现
// 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)$。
关键点总结
[!green]
- 下标
u表示已决定的元素数量，路径t表示这些元素中被选中的部分。- 每个元素的选与不选构成完整且互斥的划分，不需要额外的去重集合。
- 本实现只在所有元素决定完后收集结果，空集也会自然经过这个终止条件。
易错点总结
[!yellow]
- 叶子处直接保存路径引用，后续修改可能覆盖已保存的结果，应复制元素。
- 共享可变路径完成选择分支后要恢复，避免影响其他分支的状态。
- 空输入的幂集仍包含空集，不能直接当作没有任何子集。
- 时间开销不仅来自访问决策树，还包括复制并输出所有子集的元素。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 90. 子集 II | 中等 | 输入含重复值时要处理相同元素选择造成的重复子集，本题元素互异。 |
| 46. 全排列 | 中等 | 同样回溯枚举，本题每个元素只决定选不选，排列题还要决定位置顺序。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！