#78
中等
中频
回溯子集
这是一道围绕数组展开的高频练习。建议先掌握「回溯」这套写法，再结合下方步骤讲解理解状态维护、边界处理和复杂度取舍。
数组
题目分析
给你一个不含重复元素的数组，要求返回它的所有子集。
子集里的元素顺序不重要，数组中的每个元素都可以选择“放进去”或者“不放进去”。
一句话概括：
对每个元素做一次选或不选的决定，把所有可能结果都枚举出来。
接下来怎么看推荐代码： 带着这个理解再看推荐代码时，重点观察这条主线：用回溯维护当前子集，对每个位置做“选它”或“跳过它”的扩展。
推荐代码
推荐解法：回溯
时间复杂度： O(n * 2^n)
空间复杂度： O(n)
核心思路： 用回溯维护当前子集，对每个位置做“选它”或“跳过它”的扩展。
class Solution {
public List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> answer = new ArrayList<>();
List<Integer> path = new ArrayList<>();
dfs(nums, 0, path, answer);
return answer;
}
private void dfs(int[] nums, int start, List<Integer> path, List<List<Integer>> answer) {
answer.add(new ArrayList<>(path));
for (int i = start; i < nums.length; i++) {
path.add(nums[i]);
dfs(nums, i + 1, path, answer);
path.remove(path.size() - 1);
}
}
}结构化讲解
面试时怎么讲
开场思路
这题我会用回溯。每一层决定接下来把哪个元素加入当前子集。
核心过程
- 当前路径本身就是一个合法子集，所以先加入答案。
- 从
start开始枚举后续元素，选择一个加入路径。 - 递归进入下一层继续扩展剩余元素。
- 返回时撤销选择，继续尝试当前层的其他元素。
复杂度总结
时间复杂度 O(n * 2^n)，空间复杂度 O(n)，不计答案存储。
面试补一句：子集题和排列题最大的区别，是每一层从后缀开始选，而不是从全体未用元素里选。
核心思路
子集问题的关键是枚举每个元素“在不在答案里”。回溯里，路径表示当前已选元素，递归层表示接下来从哪个位置继续做选择。
步骤讲解
1
先把当前路径加入答案
每进入一层递归，当前路径本身就是一个合法子集，先复制收集。
为什么这样做：子集题不要求固定长度，所以每个中间状态都应该算答案。
对应代码提示：answer.add(new ArrayList<>(path));
2
从当前位置开始尝试加入下一个元素
循环遍历后续元素，把其中一个加入当前路径。
为什么这样做：这样可以保证子集按索引递增构造，避免重复生成。
对应代码提示：for (int i = start; i < nums.length; i++) { ... }
3
递归扩展并撤销选择
加入元素后进入下一层，返回时再把它弹出，恢复现场。
为什么这样做：只有回到原状态，才能继续尝试当前层的其他元素。
对应代码提示：path.add(nums[i]); dfs(i + 1); path.remove(path.size() - 1);
易错点
没先收集当前路径
这样只会得到完整长度的路径，漏掉大量中间子集。
正确理解：进入递归后第一件事就是把当前路径加入答案。
递归起点没往后推进
如果下一层还从当前索引开始，会重复选择同一个元素。
正确理解：递归时传
i + 1，表示后续只看右边元素。忘记撤销选择
后续分支会继承错误路径，答案结构就乱了。
正确理解：保持标准回溯顺序：加入、递归、删除。
复杂度与适用判断
时间复杂度：O(n * 2^n)
空间复杂度：O(n)
比其他方案更好在哪里：比枚举二进制位更容易和组合、排列类题共享同一套回溯模板。
适用判断：当题目要求列出所有组合/子集，且顺序不重要时，优先考虑回溯。
额外提醒
- 子集题里每个中间路径都算有效答案。