题目描述
返回数组(元素互不相同)的所有子集(幂集)，不能有重复。
nums = [1, 2, 3]
输出 = [], [1], [2], [3], [1,2], [1,3], [2,3], [1,2,3]
思路解析
子集数量本来就是 2ⁿ，躲不开。关键是咋系统地枚举，既不漏掉，也不会出现 [1,2] 和 [2,1] 这种重复。
从空集出发，每走到一个节点就把当前 path 记为一个子集；然后只从「上次选的位置之后」继续选下一个数（start 索引），这样保证每个子集元素递增、绝不重复。选完撤销，回头试别的。
起点 · 记录空集：一开始 path 空，先把空集 [] 记进结果——它也是一个合法子集。
选 1：选 1，path=[1]，立刻记录。接下来只能从 1 后面（2、3）里选。
再选 2：在 [1] 基础上选 2，path=[1,2]，记录。继续只能往后选 3。
再选 3：再选 3，path=[1,2,3]，记录。后面没数可选了，这条路走到底，开始回溯。
撤销回到 [1] · 选 3：撤销 3、撤销 2，回到 [1]。这次跳过 2 直接选 3，得到 [1,3] 并记录。
回到根 · 选 2：彻底撤回到空，从 2 开头：path=[2] 记录。注意不会再选 1（start 在 2 后面），所以不会出现 [2,1]。
选 2 后选 3：在 [2] 后选 3，得 [2,3] 记录。
最后 · 选 3：回到根，从 3 开头：[3]。8 个子集全部集齐，结束。
回溯就是在决策树上 DFS：进入一个分支前「做选择」、退出时「撤销选择」。子集、组合、排列、分割都是它。
参考代码（Python）
Python
1res = []
2def backtrack(start, path):
3 res.append(path[:]) # 每个节点都是一个子集
4 for i in range(start, len(nums)): # 只从 start 往后选
5 path.append(nums[i]) # 选
6 backtrack(i + 1, path) # 往后递归
7 path.pop() # 撤销
8backtrack(0, [])复杂度分析
- 时间复杂度：O(n · 2ⁿ) —— 2ⁿ 个子集，每个复制 O(n)
- 空间复杂度：O(n) —— 递归深度 + path
套路模板
记住骨架：选→递归→撤销。组合/子集用 start 去重；排列用 used 数组；允许复用就递归传 i 而非 i+1。
Python
1def backtrack(start, path):
2 if 满足结束条件: res.append(path[:]); return # 或每节点都收集
3 for i in range(start, n):
4 path.append(choices[i]) # ① 选
5 backtrack(i + 1, path) # ② 递归(i+1去重/i可复用)
6 path.pop() # ③ 撤销易错点
- ❌ res.append(path) → ✅ res.append(path[:]) 存副本（path 后面会变，直接存会被改掉）
- ❌ 不用 start，每次从 0 选 → ✅ 从 start 开始选（否则出现 [1,2] 和 [2,1] 重复）
以上文字与上方动画完全同一思路：先看动画建立直觉 → 读文字巩固 → 关掉页面自己默写一遍代码，能写出来才算真的掌握。