78. 子集（Subsets）¶
频次 ★★★★★ · 难度 🟡 · 高频：全厂
题目¶
数组元素互异，返回所有子集（含空集）。
示例：
思路¶
回溯（选或不选）：每层决定是否取当前元素，递归到数组末尾时收集。关键在于每层都有一个起始 start，避免回头（组合数，不是排列）。
代码¶
public List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
backtrack(nums, 0, new ArrayList<>(), 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);
}
}
复杂度¶
- 时间：O(n × 2^n) —— 2^n 个子集，每个拷贝 O(n)
- 空间：O(n) —— 递归栈 + path
边界条件¶
- 空数组：返回
[[]] - 单元素：返回
[[],[1]]
收账位置：答案住在决策树的哪里¶
组合型（77/216/39/40/131）答案住在叶子（选满/切完才成立）→ if (条件) 收账 + return。
子集型（78/90）答案住在每个节点（任意前缀都是子集）→ 无条件 res.add 放方法第一行，for 天然终止就是出口。
若写成 77 惯性的"先 if 出口再 add"，最深的前缀（如 [1]）住在 start==n 那层，在 add 前就 return 了 → 漏收叶子子集。
变式¶
- 90. 子集 II：含重复元素，排序 + 剪枝
i > start && nums[i] == nums[i-1] - 46. 全排列：每次从 0 开始遍历（排列），本题从 start 开始（组合）
- 迭代增量法：初始
[[]]，每遍历一个元素，给当前所有子集加上该元素——比回溯更省代码但不是面试预期解法
易错点¶
res.add(new ArrayList<>(path))放在递归开始而不是 base case——每个节点的路径都是合法子集，不是只有叶子节点才是- 组合类回溯用
start防止回头，保证[1,2]和[2,1]不会被同时收集 - 不用 visited 数组，因为 start 已经限制了选择范围
面试追问¶
- 子集问题的本质？ 每个元素选或不选，2^n 种可能。可用位运算表示：二进制 0~2^n-1 的每一位对应一个元素的取舍
- 什么时候用 start 什么时候用 visited？ 组合/子集用 start 防止回头，排列用 visited 保证全部可选——判断标准是"顺序重不重要"