LeetCode 78. 子集
题目描述
✅ 78. 子集
题意分析
给定一个元素互不相同的数组，返回它的全部子集，包括一个元素也不选的空集，以及选择全部元素的原集合。每个元素最多选一次，子集之间不能重复，答案不要求按特定顺序返回。
子集只关心选中了哪些元素，不区分选择先后。为了让同一个子集只生成一次，可以统一按原数组下标递增的顺序选择元素；这只是规定一种枚举顺序，不需要给数组按数值排序。
解法：回溯枚举
核心思路
[!blue]
用
path保存当前已经选中的元素，用start表示下一次允许选择的最小下标。每进入一次递归，当前路径本身就是一个合法子集，应立即复制到答案中。第一次进入时路径为空，因此空集也会自然被保存。接下来枚举
i从start到数组末尾，把nums[i]作为当前子集的下一个元素，并递归搜索i + 1之后的选择。没有被选中的更小下标，在这条分支里就不再考虑；之后只往后选，使每个下标最多使用一次，也不可能用不同选择顺序重复生成同一个子集。为什么不会遗漏？任意一个子集的下标都可以唯一地排成递增顺序，递归的每一层都能选到这个顺序中的下一个下标。选择完这些元素后，对应的路径就会在那一层被保存；不需要等到数组末尾，因此所有长度的子集都能被收集。
递归返回后，删除刚刚追加的末尾元素，使
path回到本层选择之前的状态，再尝试同层的其他下标。start已经限制了后续选择范围，所以这里不需要额外的used数组。保存答案时必须复制路径，因为后续分支会继续修改同一个路径容器。Java 创建新的列表，Go 复制到新的底层数组，才能保留保存时的子集内容。当
start到达数组末尾，当前路径仍先保存，随后循环自然不执行，结束这一层。
解题步骤
- 初始化空结果集与空路径，从
start = 0开始回溯。- 每次进入递归，先复制当前
path并加入答案。- 枚举
[start, n)中的下标i，把nums[i]加入路径。- 以
i + 1为下一层起点继续递归，只允许选择更靠后的元素。- 递归返回后删除路径末尾元素，继续尝试同层的下一个选择。
代码实现
class Solution {
public List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> ans = new ArrayList<>();
backtrack(nums, 0, new ArrayList<>(), ans);
return ans;
}
private void backtrack(int[] nums, int start, List<Integer> path, List<List<Integer>> ans) {
// 每个递归状态都对应一个子集，空路径也要保存副本。
ans.add(new ArrayList<>(path));
for (int i = start; i < nums.length; i++) {
path.add(nums[i]);
// 下标严格向后，避免同一元素重复使用和排列式重复。
backtrack(nums, i + 1, path, ans);
path.remove(path.size() - 1);
}
}
}
func subsets(nums []int) [][]int {
ans := make([][]int, 0)
path := make([]int, 0)
var backtrack func(int)
backtrack = func(start int) {
// 每个递归状态都对应一个子集，空路径也要保存副本。
ans = append(ans, append([]int(nil), path...))
for i := start; i < len(nums); i++ {
path = append(path, nums[i])
// 下标严格向后，避免同一元素重复使用和排列式重复。
backtrack(i + 1)
path = path[:len(path)-1]
}
}
backtrack(0)
return ans
}
复杂度分析
- 时间复杂度：$O(n \cdot 2^n)$，每个元素都有选与不选两种可能，共有 $2^n$ 个子集，复制每个子集最多需要 $O(n)$。
- 空间复杂度：辅助空间为 $O(n)$，用于递归栈与当前路径；返回结果本身需要 $O(n \cdot 2^n)$ 空间。
关键点总结
[!green]
- 空集也是答案，因此进入每层递归时就收集当前路径。
- 递归传入
i + 1，用递增下标避免重复枚举。- 答案必须保存
path的副本，共享路径在回溯过程中会继续变化。
易错点总结
[!yellow]
- 直接保存路径而不复制，会让答案与仍在修改的路径共享数据，后续回溯可能破坏已有结果。
- 忘记撤销末尾元素，会让上一分支的状态污染下一分支。
- 下一层仍从
start或i开始，会重复使用当前元素。- 只在叶子节点收集，会漏掉空集和较短的子集。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 90. 子集 II | 中等 | 输入允许重复时，需要额外剪掉相同选择，本题元素互异。 |
| 77. 组合 | 中等 | 在全部子集枚举上增加大小必须等于k的限制，可按剩余数量剪枝。 |
| 补充题 205. 数组的全部子集 | 中等 | 都用回溯逐个决定元素是否进入子集；补充题还要求子集内按非降序排列。 |
| 39. 组合总和 | 中等 | 在选择和撤销之间枚举组合；本题输出所有选择长度的子集，该题允许同一候选被多次选取。 |
| 40. 组合总和 II | 中等 | 在选择和撤销之间枚举组合；本题输出所有选择长度的子集，该题候选只能用一次且需去重。 |
| 216. 组合总和 III | 中等 | 在选择和撤销之间枚举组合；本题输出所有选择长度的子集，该题固定元素数量且只取一到九。 |
| 补充题 117. 目标和非空子序列的枚举 | 中等 | 列出所有目标和非空子序列。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！