LeetCode LCR 079. 子集
题目描述
题意分析
返回互不相同的数组元素组成的所有子集，包含空集。子集不区分选取顺序，每种元素集合只输出一次；不要求子集中的数值按大小排列。
解法：递增下标回溯子集
核心思路
[!blue]
每个子集都可以唯一地写成下标递增的选择序列。用
start表示下一次可选的最小下标，本层枚举i >= start，选中nums[i]后从i + 1继续。这样既不会重复使用同一个元素，也不会把同一子集的不同选取顺序重复输出。
path保存当前选中的元素。每次进入递归时，它已经是一个合法子集，所以应立即保存，不必等到选满所有元素。最初的空路径正好生成空集；当后面没有元素可选时，循环自然结束。同一份
path会被递归反复修改。进入子分支前追加一个元素，返回后删除末项，让下一个分支从原状态开始；加入答案时则复制当前路径，避免后续修改影响已经保存的子集。
解题步骤
- 创建结果和空路径，从
start = 0开始递归。- 每次进入递归，先将当前路径的副本加入结果。
- 枚举从
start到数组末尾的下标i，追加nums[i]。- 递归处理
i + 1之后的候选，返回后删除刚追加的末项。- 循环结束即返回上一层，最终得到全部子集。
代码实现
class Solution {
public List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
List<Integer> path = new ArrayList<>();
backtrack(nums, 0, path, res);
return res;
}
private void backtrack(int[] nums, int start, List<Integer> path, List<List<Integer>> res) {
// 当前路径本身就是一个子集，需要先收集。
res.add(new ArrayList<>(path));
for (int i = start; i < nums.length; i++) {
path.add(nums[i]);
backtrack(nums, i + 1, path, res);
path.remove(path.size() - 1);
}
}
}
func subsets(nums []int) [][]int {
res := make([][]int, 0)
path := make([]int, 0)
var backtrack func(start int)
backtrack = func(start int) {
// 当前路径本身就是一个子集，需要先收集。
subset := append([]int(nil), path...)
res = append(res, subset)
for i := start; i < len(nums); i++ {
path = append(path, nums[i])
backtrack(i + 1)
path = path[:len(path)-1]
}
}
backtrack(0)
return res
}
复杂度分析
- 时间复杂度：$O(n2^n)$。共有 $2^n$ 个子集，每个都要复制到结果中；全部子集的元素总数为 $n2^{n-1}$。
- 空间复杂度：不计结果为 $O(n)$，用于递归栈和路径；输出本身需要 $O(n2^n)$ 空间。
关键点总结
[!green]
- 每条递增下标路径对应一个子集，输入值互异保证不同下标集合不会得到相同答案。
- 答案在搜索树的每个节点，不只是叶节点；空路径也必须收集。
start控制后续选择范围，不需要额外used数组。
易错点总结
[!yellow]
- 只在走到数组末尾时收集，会漏掉不包含最后一个元素的子集。
- 下一层必须从
i + 1开始；传i会重复选当前元素，传原起点会重新生成排列。- 返回后删除路径末项，不能按当前数值误删其他位置。
- 结果里必须保存独立副本，不能直接保存可变路径或其视图。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 90. 子集 II | 中等 | 输入允许重复时，需要额外剪掉相同选择，本题元素互异。 |
| 77. 组合 | 中等 | 在全部子集枚举上增加大小必须等于k的限制，可按剩余数量剪枝。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！