子集

🟡 Medium · 🏷️ 数组、回溯、位运算 · LeetCode#78

📖 题目

给一个不含重复元素的数组，返回它所有可能的子集（幂集），包括空集和它本身。

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

💡 思路

方法一（迭代）：每来一个新数字，把它加到已有的每个子集上，就得到了一批新子集——子集数量每轮翻倍，最后是 2ⁿ 个。

初始:  [[]]
遇到1: [[], [1]]
遇到2: [[], [1], [2], [1,2]]
遇到3: [[], [1], [2], [1,2], [3], [1,3], [2,3], [1,2,3]]

方法二（回溯）：回溯题的通用做法是先画决策树，再写代码——树画出来，代码基本就是把树翻译成 Python。子集问题的树是这样的：从数组里按顺序选数字加入路径，start 保证只往后选（不回头，避免 [1,2] 和 [2,1] 被当成两个不同结果）：

                    []                start=0，选1/2/3
                /    |    \
             [1]    [2]    [3]       start=1/2/3
            /   \     |
        [1,2]  [1,3] [2,3]           start=2/3
          |
      [1,2,3]                        start=3，没得选了

每个节点都是一个合法子集，不用等走到叶子——这点和后面会遇到的"排列"不一样，排列只有走到叶子（长度等于n）才算一个完整结果。

对应到代码：进入一个节点就先记录当前路径；for i in range(start, n) 是这个节点的所有分支；选一个数就 append 往下递归；递归回来后 pop() 撤销这次选择，尝试下一个分支——这一步"撤销"就是"回溯"这个名字的来源。

💻 代码

方法一：迭代（更简洁）

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        output = [[]]
        for n in nums:
            output += [a + [n] for a in output]
        return output

a + [n] 创建新列表，不修改原列表——跟之前路径收集里"传新列表 vs 修改原列表"是同一个道理。

方法二：回溯（通用模板，后面排列、组合都是它的变体）

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        result = []

        def backtrack(start, path):
            result.append(path[:])              # 每个节点都记录
            for i in range(start, len(nums)):
                path.append(nums[i])            # 做选择
                backtrack(i + 1, path)           # 只往后选
                path.pop()                        # 撤销选择

        backtrack(0, [])
        return result

两种方法复杂度相同：时间 O(n × 2ⁿ)（2ⁿ 个子集，每个平均要复制 n/2 长度），空间 O(n × 2ⁿ)。