LeetCode 78：子集，从搜索树推出 startIndex 回溯模板

题目要求

输入输出

• 输入：nums，长度 1 <= nums.length <= 10
• 元素范围：-10 <= nums[i] <= 10
• 所有元素互不相同
• 输出：返回 nums 的所有可能子集
• 顺序：结果顺序不限，子集内部不需要考虑排列顺序

示例

输入：nums = [1,2,3]
输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

这篇只用 Python 构造一个最小可运行解法。

从 [1,2] 的搜索树开始

最小但有分叉的例子是：

nums = [1,2]

答案应该是：

[], [1], [1,2], [2]

注意这里没有 [2,1]。这说明问题不是“随便排列所有选择”，而是“每个元素选或不选，且同一组元素只出现一次”。

如果把构造过程画成树：

[]
|- [1]
|  |- [1,2]
|- [2]

这棵树暴露出两个事实：

• 每个节点都是一个合法子集。
• 进入 [1] 之后，后面只能继续看 2，不能回头再选 1 或生成 [2,1]。

Step 1：先说清楚一个递归层在解决什么

如果当前已经选出一个 path，剩下的问题是：

从某个起点之后的元素里，继续选择若干个元素，扩展当前 path。

这个“某个起点”必须被记下来。否则 [1,2] 和 [2,1] 会从不同路径重复出现。

先写最小骨架。它只保留两个状态：

• path：当前分支已经选了什么
• res：已经收集到的所有子集

def subsets(nums: list[int]) -> list[list[int]]:
    res: list[list[int]] = []
    path: list[int] = []

    def dfs(start: int) -> None:
        pass

    dfs(0)
    return res

现在这个版本能做到：

• 明确外层函数和递归函数的接口。
• 给递归层预留 start，表示当前层从哪里继续选。

它还缺：

• 什么时候收集答案。
• 当前层如何枚举选择。

Step 2：每个节点都是答案，所以先收集当前 path

在上一版基础上，给 dfs 增加第一条规则：

def dfs(start: int) -> None:
    res.append(path.copy())

为什么是一进入递归就收集？

因为子集不要求“选满多少个元素”。当前 path 只要由原数组元素按顺序构成，就是一个合法子集。

为什么要 copy()？

因为 path 后面会继续增删。如果直接把 path 放进 res，历史答案会跟着后续回溯一起变。

现在这个版本能做到：

• 收集空集 []。
• 收集任意进入递归层时的当前路径。

它还缺：

• 还没有向下扩展，所以只能拿到空集。

Step 3：当前层只能从 start 往后枚举

在上一版基础上，给 dfs 加当前层的候选范围：

def dfs(start: int) -> None:
    res.append(path.copy())

    for i in range(start, len(nums)):
        pass

这里 range(start, len(nums)) 的含义是：

• 当前层只能选择下标 start 及其右侧的元素。
• 更左侧的元素已经在前面的路径里处理过，不再回头。

对 nums = [1,2,3]：

• dfs(0) 可以尝试 1,2,3
• 选了 1 后进入 dfs(1)，只能尝试 2,3
• 选了 2 后进入 dfs(2)，只能尝试 3

现在这个版本能做到：

• 明确每一层有哪些候选元素。
• 用 start 避免倒序重复。

它还缺：

• 还没有真正把候选元素加入路径。

Step 4：选中一个元素后，递归处理右侧剩余元素

在上一版基础上，把循环体里的一个候选加入 path，然后递归到右侧：

for i in range(start, len(nums)):
    path.append(nums[i])
    dfs(i + 1)

这里 dfs(i + 1) 是关键。它表达的是：

当前元素已经被选入 path，下一层只能从它右边继续选。

如果这里写成 dfs(start + 1)，当 i 不等于 start 时边界就错了。真正应该推进的是“当前选中的下标”。

现在这个版本能做到：

• 生成 [] -> [1] -> [1,2] 这样的向下路径。
• 保证子集内部按原数组下标递增。

它还缺：

• 递归回来以后没有撤销选择，会污染同层后面的分支。

Step 5：递归回来后撤销选择，得到完整解法

在上一版基础上，递归返回后把刚选的元素弹出：

for i in range(start, len(nums)):
    path.append(nums[i])
    dfs(i + 1)
    path.pop()

这一步解决的是“分支之间不能共享临时选择”的问题。

以 nums = [1,2,3] 为例：

path = [1,2,3] 收集后返回
pop 3 -> path = [1,2]
pop 2 -> path = [1]
继续同层尝试 3 -> path = [1,3]

如果没有 path.pop()，从 [1,2,3] 回到上一层后，路径仍然带着 3，后面的分支会全部错乱。

这一版已经是完整可运行代码：

class Solution:
    def subsets(self, nums: list[int]) -> list[list[int]]:
        res: list[list[int]] = []
        path: list[int] = []

        def dfs(start: int) -> None:
            res.append(path.copy())

            for i in range(start, len(nums)):
                path.append(nums[i])
                dfs(i + 1)
                path.pop()

        dfs(0)
        return res


if __name__ == "__main__":
    ans = Solution().subsets([1, 2, 3])
    print(ans)

现在这个版本能做到：

• 枚举所有子集。
• 不产生 [2,1] 这类顺序重复。
• 每个递归分支结束后恢复现场。

它还缺：

• 对重复元素的处理。这个问题在 90. 子集 II 里单独解决。

慢速走一条分支

用 nums = [1,2,3] 看一条路径：

dfs(0), path = []
收集 []

i = 0, 选择 1
path = [1]
dfs(1), 收集 [1]

i = 1, 选择 2
path = [1,2]
dfs(2), 收集 [1,2]

i = 2, 选择 3
path = [1,2,3]
dfs(3), 收集 [1,2,3]

返回，pop 3 -> [1,2]
返回，pop 2 -> [1]
同层继续 i = 2, 选择 3 -> [1,3]

这个 trace 要看的不是答案顺序，而是两个不变量：

• path 始终表示当前搜索分支。
• start 始终保证下一层只看右侧剩余元素。

正确性

不变量：

• dfs(start) 开始时，path 是一个由 nums 中若干元素按下标递增组成的合法子集。
• 当前层只会从 start 到末尾选择元素，所以不会生成倒序重复。

为什么不会漏：

• 对任意一个子集，把它的元素按原数组下标从小到大排列。
• DFS 会沿着这些下标依次选择它们，因此这个子集一定会被访问。

为什么不会重：

• 每条路径的下标严格递增。
• 同一组下标只能由唯一一条递增路径生成。

复杂度

• 子集数量是 2^n。
• 每次收集答案需要复制 path，总复制成本是 O(n * 2^n)。
• 递归栈和 path 的额外空间是 O(n)；输出本身占 O(n * 2^n)。

常见错误

• 只在叶子节点收集答案，会漏掉 []、[1]、[1,2] 这类中间节点。
• 忘记 path.copy()，导致 res 里的答案被后续回溯修改。
• 递归写成 dfs(start + 1)，边界没有跟着当前选择的下标走。
• 忘记 path.pop()，导致分支状态污染。

小结

• 子集题的核心不是叶子节点，而是“每个搜索树节点都是答案”。
• path 表示当前分支，start 表示下一层从哪里继续选。
• dfs(i + 1) 保证组合不倒序重复。
• path.pop() 保证回溯后同层分支互不污染。

参考与延伸

• LeetCode 78：Subsets
• LeetCode 90：Subsets II
• LeetCode 46：Permutations

Notes

• 题意、示例和约束来自当前仓库旧稿中的 LeetCode 78 摘要。
• 代码语言按本仓库当前 LeetCode 教程默认选择 Python。