题目描述
思路解析
一句话答案：LeetCode 78 子集的标准解是回溯：维护路径 path，从下标 start 往后逐个「选择→递归→撤销」，并且每进入一个递归节点就把当前 path 复制一份收进结果——空集、单元素、全集都由此产生。n 个元素共 2ⁿ 个子集，每个复制花 O(n)，总时间 O(n·2ⁿ)，递归栈空间 O(n)。
子集问题的解空间有多大
每个元素只有两种命运：进当前子集，或不进。n 个元素的取舍彼此独立，组合起来一共 2ⁿ 个子集，空集和全集都算数。示例 [1,2,3] 正好 8 个。既然要求输出全部子集，任何算法都至少要把这 2ⁿ 个结果各生成一遍，指数级不可避免——问题只剩下：怎么枚举得不重、不漏、代码还短。
为什么用回溯而不是写循环
两层、三层嵌套循环只能枚举固定长度的组合，而子集长度从 0 到 n 都有，循环层数根本写不死。回溯（backtracking）用递归把「逐个元素决定选不选」展开成一棵搜索树：path 记录当前已选的元素，向下走一步等于多选一个数，这条分支探完就把刚选的数弹出来复原，换下一个分支。「选择→递归→撤销」三拍循环，让同一条 path 反复复用于所有分支，省去每次重建的开销。
start 参数为什么能保证不重不漏
子集是组合不是排列，[1,2] 和 [2,1] 算同一个。防重的手法是给递归传 start：每层只从 start 往后挑，选中下标 i 之后，下一层从 i + 1 起步，绝不回头。这样任何子集内部的下标都严格递增，而「一个子集」和「它按下标升序的选取路径」一一对应——每个子集恰好被生成一次，也不会有谁被跳过。这是所有组合类回溯题共用的去重套路。
为什么每个节点都收集而不只在叶子收
很多回溯题只在「凑满条件」的叶子处收集答案，本题不同：搜索树上每一个节点手里的 path 本身就是一个合法子集——空 path 对应空集，走了一步的 path 对应单元素子集。所以递归一进门就先收集，正好把 2ⁿ 个子集一一收齐，一个不多一个不少。
收集时必须存副本，写 res.append(path[:]) 而不是 res.append(path)：path 自始至终是同一个列表引用，后续的撤销操作会把已经存进结果里的内容一并改掉，这是本题最隐蔽的坑。
复杂度怎么数，还有别的枚举法吗
子集共 2ⁿ 个，每个收集时要花 O(n) 复制，总时间 O(n·2ⁿ)；递归深度和 path 长度都不超过 n，辅助空间 O(n)，不计结果本身。两个常见延伸：若数组含重复元素（LC90 子集 II），先排序，同一层遇到与前一个相同的值就跳过；不想写递归可以用位掩码枚举——把 0 到 2ⁿ - 1 的每个整数看作一种选取方案，二进制某位为 1 就选对应元素，复杂度相同，但少了递归的直观结构。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
记住这条：选→收集→递归→撤销，start 防重复。下面逐帧看它怎么跑。
从空 path 出发——空集 [] 也是合法子集，先记下它（第 1 个）。
从下标 0 起往后选：选中 1，path 变成 [1]。用 start=0 保证只往后挑，不会回头选出 [1,…] 的重复排列。
走到一个节点，把当前 path=[1] 记成一个子集（第 2 个）。每个节点都收集，所以空集也算。
从下标 1 起往后选：选中 2，path 变成 [1,2]。用 start=1 保证只往后挑，不会回头选出 [2,…] 的重复排列。
走到一个节点，把当前 path=[1,2] 记成一个子集（第 3 个）。每个节点都收集，所以空集也算。
从下标 2 起往后选：选中 3，path 变成 [1,2,3]。用 start=2 保证只往后挑，不会回头选出 [3,…] 的重复排列。
走到一个节点，把当前 path=[1,2,3] 记成一个子集（第 4 个）。每个节点都收集，所以空集也算。
这条分支走到底，撤销 3（path 弹出），回到 [1,2]。回溯=进入选、退出撤销，让 path 复位去试下一个分支。
这条分支走到底，撤销 2（path 弹出），回到 [1]。回溯=进入选、退出撤销，让 path 复位去试下一个分支。
从下标 2 起往后选：选中 3，path 变成 [1,3]。用 start=2 保证只往后挑，不会回头选出 [3,…] 的重复排列。
走到一个节点，把当前 path=[1,3] 记成一个子集（第 5 个）。每个节点都收集，所以空集也算。
这条分支走到底，撤销 3（path 弹出），回到 [1]。回溯=进入选、退出撤销，让 path 复位去试下一个分支。
这条分支走到底，撤销 1（path 弹出），回到 [ ]。回溯=进入选、退出撤销，让 path 复位去试下一个分支。
从下标 1 起往后选：选中 2，path 变成 [2]。用 start=1 保证只往后挑，不会回头选出 [2,…] 的重复排列。
走到一个节点，把当前 path=[2] 记成一个子集（第 6 个）。每个节点都收集，所以空集也算。
从下标 2 起往后选：选中 3，path 变成 [2,3]。用 start=2 保证只往后挑，不会回头选出 [3,…] 的重复排列。
走到一个节点，把当前 path=[2,3] 记成一个子集（第 7 个）。每个节点都收集，所以空集也算。
这条分支走到底，撤销 3（path 弹出），回到 [2]。回溯=进入选、退出撤销，让 path 复位去试下一个分支。
这条分支走到底，撤销 2（path 弹出），回到 [ ]。回溯=进入选、退出撤销，让 path 复位去试下一个分支。
从下标 2 起往后选：选中 3，path 变成 [3]。用 start=2 保证只往后挑，不会回头选出 [3,…] 的重复排列。
走到一个节点，把当前 path=[3] 记成一个子集（第 8 个）。每个节点都收集，所以空集也算。
这条分支走到底，撤销 3（path 弹出），回到 [ ]。回溯=进入选、退出撤销，让 path 复位去试下一个分支。
边界三连：空集永远在，n 个元素恒有 2ⁿ 个。
两个高频追问：去重变体 + 位掩码解法。
参考代码
def subsets(nums): res = [] def backtrack(start, path): res.append(path[:]) # 每个节点都收集一个子集 for i in range(start, len(nums)): path.append(nums[i]) # 选 i backtrack(i + 1, path) # 只从 i+1 往后，避免重复 path.pop() # 撤销，回溯 backtrack(0, []) return res复杂度
- 时间：O(n·2ⁿ)，2ⁿ 个子集，每个最长 n，复制要 O(n)
- 空间：O(n)，递归深度 + path 长度，不计结果存储
易错点
面试追问把动画讲成自己的话
追问如果 nums 含重复元素（LC90 子集 II）怎么办？
追问不用回溯还能怎么枚举子集？
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
组合总和
LeetCode 39 · 中等 · 沿着 回溯 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题