子集
Subsets
返回数组的所有子集（幂集），不能有重复子集。
在力扣中练习题目描述
给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。
解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
示例 1：
输入：nums = [1,2,3] 输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
示例 2：
输入：nums = [0] 输出：[[],[0]]
提示：
1 <= nums.length <= 10-10 <= nums[i] <= 10nums中的所有元素 互不相同
解题思路
回溯 · 每个节点收集
先收当前 path，再决定下一个选谁
子集问题可以看成一棵决策树：每个节点都代表一个已经做出的选择，因此每个节点都是一个合法子集，而不是只有叶子。
为了不重复，递归时带一个 start，下一层只能从当前下标之后选。这样 [2,5] 和 [5,2] 只会出现一次，也不需要额外去重。
空集也是子集；从 start 开始，每次选一个数并只往后递归，顺序不同的重复子集就不会出现。
自拟数组 [2,5,7] 三个元素，共 2³ = 8 个子集。画面上 array 的灰色部分是已经不能选的下标，path 是当前子集，res 每进入一个节点就追加一次。
到达一个搜索节点，当前 path [2, 5, 7] 就是一个子集，复制进 res。
- res.size
- 4
每个元素在每条分支上只有“选 / 不选”两种状态，时间 O(n·2ⁿ)（复制结果占主导），递归深度 O(n)。
易错点
- 只在叶子收集：会漏掉所有中间子集，包括空集。
- 下一层从 0 开始：会出现 [2,5] 与 [5,2] 等重复排列。
- 忘记 path.pop_back()：不同分支互相污染。
二进制掩码 · 枚举
用 n 位二进制表示每个元素选不选
实现最短，但必须能按下标访问；结果数量仍是 2ⁿ，适合 n 很小的场合。
n 个元素，每个元素有“选/不选”两种状态，正好对应一个 n 位二进制数。枚举 0 .. 2ⁿ-1，第 i 位为 1 就把 nums[i] 放进当前子集。
它不需要递归，也不会产生重复；缺点是必须一次性知道 n，而且结果规模固定为 2ⁿ。
当 n 超过 20 左右时，2ⁿ 已经无法承受，这时应该考虑题目是否真的需要枚举所有子集。
- 1枚举 mask 从 0 到 2ⁿ-1。
- 2检查每一位是否为 1。
- 3把对应元素加入当前子集。
- 4收集当前子集。
易错点
- 1 << n 用 int：n 较大时溢出，必要时用 long long。
- 位序与数组下标对应错：结果顺序不同但仍合法，需确认题目要求。
代码与演示
主解法配有图解；对照解法用于比较思路、复杂度或实现方式。
nums = [2,5,7]空集也是子集；从 start 开始，每次选一个数并只往后递归，顺序不同的重复子集就不会出现。
查看 C++ 代码
延伸阅读
- 子集、组合、排列的区别在“什么时候收集”和“下一层从哪开始”：子集每个节点收集，组合叶子收集，排列用 used。
- 去重的通用做法是先排序，再在同一层跳过相同元素。