Leetcode Hot 100 刷到这题，回溯味又浓起来了：子集。
这类题有个很经典的脑回路：
每个元素都面临一个灵魂拷问：你，到底选不选？
一旦把这个问题想明白，这题基本就已经解开一半。
因为子集问题的本质就是：
- 对每个元素做决策
- 决策只有两种
- 选
- 不选
于是整道题就会自然长成一棵二叉决策树。
而这，也正是回溯最擅长收拾的地盘。
题目链接
题目描述
给你一个整数数组 nums ，数组中的元素 互不相同。
返回该数组所有可能的子集（幂集）。
解集不能包含重复的子集。你可以按任意顺序返回解集。
解题思路：回溯，选或不选
这题最直观的写法，就是对每个元素做一次二选一：
- 选进当前子集
- 不选进当前子集
假设当前递归处理到下标 i，那么面对 nums[i] 时，我们只有两个动作：
1. 选它
把 nums[i] 加入当前路径 vals，再继续处理下一个元素。
2. 不选它
撤销刚才的选择（或者一开始就不加），继续处理下一个元素。
当我们走到 i == n 时，说明数组里的每个元素都已经做完决定了。
这时当前的 vals 就是一个完整合法的子集，可以加入答案。
一句话概括就是：
子集问题 = 每个数都走一遍“选 / 不选”的分叉路。
代码实现
class Solution(object): def subsets(self, nums): """ :type nums: List[int] :rtype: List[List[int]] """ n = len(nums) ans = [] vals = []
def dfs(i): if i == n: ans.append(vals[:]) return
# 选 nums[i] vals.append(nums[i]) dfs(i + 1)
# 不选 nums[i] vals.pop() dfs(i + 1)
dfs(0) return ans为什么这是标准二叉决策树
每处理一个元素，就会分成两条路：
- 选
- 不选
所以如果数组长度是 n，那么整棵递归树的深度就是 n。
每走到叶子节点一次，就对应生成一个子集。
比如 nums = [1, 2, 3]，决策树大概可以理解成这样：
[] / \ 选1 不选1 / \ / \ 选2 不选2 选2 不选2 ... ... ... ...一路走到底后，路径上留下来的那些数，就是当前子集。
回溯过程怎么理解
定义 dfs(i) 表示：
当前正在决定
nums[i]要不要进入子集。
递归终止条件
当：
i == n说明 nums 里的每一个元素都已经做过选择了。
这时就得到一个完整子集：
ans.append(vals[:])注意这里一定要用切片拷贝，别直接把 vals 本体扔进去。
不然后面继续回溯时，之前保存的结果会一起被改掉。
为什么要 vals[:] 拷贝
这又是 Python 回溯题的经典坑位。
如果你写的是：
ans.append(vals)那么加入 ans 的不是一份独立结果，
而是同一个列表对象的引用。
后面一旦执行：
vals.append(...)vals.pop()
之前保存进 ans 的内容也会被同步影响。
最后结果很可能整整齐齐，一看就知道大家共用一个宿舍。
所以必须写成：
ans.append(vals[:])相当于当前子集拍照留档，后面的回溯再折腾，也不会把旧照片改花。
为什么这里要先 pop() 再走“不选”分支
代码里这一段很关键：
vals.append(nums[i])dfs(i + 1)
vals.pop()dfs(i + 1)这里的含义是：
- 先尝试“选当前元素”
- 递归回来后，把它从路径里删掉
- 再去尝试“不选当前元素”
这个 pop() 就是在恢复现场。
如果不恢复，后面的“不选”分支其实就还带着刚才那个元素， 那就不叫不选了，叫嘴上说不选，手上却没放下。
举个例子
假设：
nums = [1, 2]递归过程可以这样理解。
从 dfs(0) 开始
当前要决定 1：
分支一：选 1
vals = [1]然后进入 dfs(1)，继续决定 2：
- 选
2→[1, 2] - 不选
2→[1]
分支二：不选 1
此时先把 1 弹出，恢复成：
vals = []然后继续决定 2：
- 选
2→[2] - 不选
2→[]
于是最终能得到四个子集：
[1, 2][1][2][]顺序可能不一样，但答案集合是相同的。
一个容易忽略的小点：空数组的答案是什么
如果 nums = []，那么它的所有子集并不是：
[]而是：
[[]]因为空集本身也是一个合法子集。
所以这题其实不需要专门写：
if n == 0: return []直接让递归走到终点，就会自然得到正确答案 [[]]。
这也是你原思路里最值得顺手修正的一点。
复杂度分析
设数组长度为 n。
时间复杂度
每个元素都有两种状态：选或不选。
所以总共会产生：
2^n个子集。
每次加入答案时，还需要复制当前路径，最坏长度是 n，
因此总时间复杂度为：
O(n × 2^n)空间复杂度
递归深度最大为 n，当前路径 vals 最多也存 n 个元素。
所以不考虑最终答案时，额外空间复杂度为：
O(n)如果算上返回结果，那答案本身就需要 O(n × 2^n) 的空间。
没办法，幂集就是这么能生。
这题的关键点
1. 每个元素只有两种选择
- 选
- 不选
这就是子集问题最核心的递归结构。
2. 回溯时要恢复现场
vals.pop()这一步不能丢。
3. Python 中收集答案必须拷贝
ans.append(vals[:])不拷贝，就等着结果集集体串味。
4. 空数组的答案是 [[]]
这个地方很容易被手滑写错。
小结
这道题是回溯模板题里的基础款，但基础款不等于随便写。
真正要记住的是这套思路：
- 每个元素都做一次“选 / 不选”的决策
- 递归走到底，就得到一个完整子集
- 回溯时恢复现场
- 收集结果时记得拷贝当前路径
如果只记一句话，那就是：
子集问题就是一棵“选或不选”的二叉树，叶子节点上的路径就是答案。
这题写顺了，回溯的门算是又推开一扇。 后面组合、分割、括号生成这些亲戚再来，就不会显得那么突然了。🦐