LC78　子集¶

中等通过率 81.8%python3核心代码模式回溯样例通过牛客 AC位运算数组回溯

一句话

每层从 start 往后挑一个元素接上去，路上经过的每个结点都是一个子集。

解题思路¶

这题考什么¶

子集（幂集）与组合是同一件事：组合题固定了长度，子集题要所有长度。所以骨架和组合题完全一样——每层只从下标 start 往后选，靠「不回头」保证同一批元素只以唯一一种顺序出现，从根上避免 [1,2] 与 [2,1] 的重复—— 唯一的差别是收答案的位置：不在叶子收，而在进入每个结点时就收一份。

nums = [1,2,3]，进入结点即收 path
    []            -> 收 []
    [1]           -> 收 [1]
      [1,2]       -> 收 [1,2]
        [1,2,3]   -> 收 [1,2,3]
      [1,3]       -> 收 [1,3]
    [2]           -> 收 [2]
      [2,3]       -> 收 [2,3]
    [3]           -> 收 [3]
共 8 = 2 的 3 次方 条

换个角度看这棵树：每个元素只有「选」与「不选」两种命运， for 循环从 start 扫到末尾，正是把「跳过若干个再选一个」摊平成同一层的兄弟分支。这与逐位枚举 0/1 掩码的位运算写法等价，回溯版的好处是天然支持带重复元素的变体。回溯的「选择 -> 递归 -> 撤销」三步见 DFS 深度优先搜索。

数据规模与复杂度¶

1 <= nums.length <= 10，元素互不相同。子集共 2 的 n 次方条，n = 10 时是 1024 条；每条平均长 n/2，拷贝一份的开销 O(n)。时间 O(n 乘 2 的 n 次方) 约 1e4 次基本操作，指数级枚举在这个量级完全够用。空间 O(n)：path 与递归栈都只有 10 层深，答案本身不计。

坑在哪¶

收答案的位置是进入结点时，不是走到叶子时。写成「start == n 才收」，只会拿到唯一一条全选的子集 [1,2,3]，长度不足的全部丢失。
每层必须从 start 往后选，不能从 0 开始扫。从 0 开始会把 [1,2] 与 [2,1] 当成两条不同的路径产出，变成排列枚举，重复解直接判错。
递归传的是 i + 1 而不是 i：每个元素在一条路径上最多用一次。传 i 会变成「元素可重复选取」（LC39 的形态），产出 [1,1,1,...] 这类无限深的分支，最终栈溢出。
收答案必须写 path[:] 做一份拷贝。path 是全程复用的同一个列表，直接追加它本身的话，res 里存的全是同一个对象的引用，回溯结束时 path 已被弹空，输出会变成一堆空列表。
空集也是子集，必须出现在答案里。本文件在 dfs 的入口无条件收 path，根结点那次收的正好是空集，不需要额外补。
本题在 meta.json 的 judge 里配了 unordered_deep：题面明写「可以按任意顺序返回解集」，解与解之间没有先后；而每个子集是集合语义，[1,2] 与 [2,1] 表示同一个子集，所以内层顺序也一并放宽。顺序放宽不等于内容放宽——同一个子集吐两遍照样判错，去重仍靠上面那条 start 下标。

样例复核¶

nums = [1,2,3] 按上图的进入顺序产出 []、[1]、[1,2]、[1,2,3]、[1,3]、[2]、[2,3]、[3]，恰好 8 条，与样例给出的 8 个子集是同一个解集（顺序不同，本题允许）。

参考实现¶

solutions/leetcode/LC78/sol.py
from typing import List, Optional


class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        n = len(nums)
        # res 收答案，path 是从根走到当前结点选出的那些元素
        res = []
        path = []

        def dfs(start: int) -> None:
            # 收答案在**进入结点时**，不在叶子：这样长度 0 到 n 的子集全都能收到
            # path[:] 是必需的拷贝，path 本身接下来还要被继续修改
            res.append(path[:])
            # 只从 start 往后挑，强制子集内部按下标递增，杜绝 [1,2] / [2,1] 的重复
            for i in range(start, n):
                path.append(nums[i])    # 选：把 nums[i] 接进当前子集
                # 递归传 i + 1：每个元素在一条路径上最多用一次
                dfs(i + 1)
                path.pop()              # 撤销：弹回来，换下一个候选接上去

        # 从下标 0 起步，根结点那次收到的正是空集
        dfs(0)
        return res

LC78 子集¶