LeetCode 78：子集（Subsets）题解

Subsets 是 LeetCode Hot 100 里面一道非常经典的回溯题。

这道题和前面的“全排列”“组合总和”“括号生成”一样，都属于回溯专题里的高频题目。 但它和前面几道题又有一个很明显的区别：

这道题不是要求你选满，也不是要求你满足某个和，而是要求你把所有可能的选择情况全部列出来。

换句话说，这道题要求的是一个数组的 幂集，也就是所有子集。

例如：

nums = [1,2,3]

它的所有子集包括：

• 什么都不选：[]

• 只选一个：[1]、[2]、[3]

• 选两个：[1,2]、[1,3]、[2,3]

• 全都选上：[1,2,3]

所以最终答案一共有 8 个。

你给出的这份 Java 代码，使用的是这道题最经典、最标准的一种写法：

回溯 + 起始下标控制

这种写法的核心非常清晰：

1. 每到一个递归状态，先把当前路径加入答案

2. 然后从当前位置往后枚举下一个可选元素

3. 选择、递归、撤销选择

4. 最终就能得到所有子集

本文就结合这段代码，系统地讲一下这道题的思路。

题目介绍

给你一个整数数组 nums，数组中的元素 互不相同。 请你返回该数组的所有可能子集，也就是它的幂集。

注意：

• 解集不能包含重复的子集

• 返回结果的顺序没有要求

例如：

nums = [1,2,3]

那么合法答案包括：

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

这道题的关键点在于：

每个元素其实都只有两种状态：选，或者不选。

所以从本质上说，这就是一个非常标准的“枚举所有选择情况”的问题。

示例

示例 1

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

数组有 3 个元素，所以总子集数量应该是：

2^3 = 8

示例 2

输入：nums = [0]
输出：[[],[0]]

只有一个元素时，子集只有两种：

• 不选：[]

• 选：[0]

为什么这道题适合用回溯？

因为“子集”本质上就是一个“逐步做选择”的过程。

假设当前数组是：

[1,2,3]

那么对于每个元素，我们都面临一个选择：

• 要它

• 不要它

从决策树角度来看，这是一棵非常典型的搜索树：

• 第一层决定要不要 1

• 第二层决定要不要 2

• 第三层决定要不要 3

最终走到树的不同位置，就会对应不同的子集。

而回溯算法最擅长处理的，正是这种“枚举所有可能决策路径”的问题。

不过这道题的代码写法，并不是显式地去写“选 / 不选”两个分支，而是用了另一种更常见、更整洁的组合式写法：

固定当前路径，然后向后枚举下一个可加入的元素。

最直接的想法是什么？

如果用最朴素的话来描述这题，思路其实很简单：

• 当前已经选了一些元素，形成一个子集

• 这个子集本身就应该加入答案

• 然后再尝试从后面的元素里继续选，形成更大的子集

• 选完之后再回退，尝试别的选择

你会发现，这正好符合回溯的经典结构：

1. 记录当前路径

2. 枚举下一步选择

3. 递归进入下一层

4. 撤销选择

所以这题几乎就是“回溯基础模板题”。

核心思路

你这段代码的核心逻辑可以概括成下面几句：

1. 当前路径本身就是一个合法子集

无论当前选了多少元素，它都是一个合法答案，所以每次进入递归函数时，都应该先把当前路径加入结果集。

2. 后续选择只能从当前位置往后开始

这是为了避免重复。

例如：

• [1,2] 和 [2,1] 本质上是同一个子集

• 所以在搜索时，我们只允许按照固定顺序向后选

• 不允许回头选前面的元素

这就是 start 参数的作用。

3. 每次选择一个新元素加入路径，再递归往下搜索

这样就能逐步生成所有不同大小的子集。

Java 代码

下面是你给出的代码，我这里保留原始逻辑，并加上注释：

class Solution {
    List<List<Integer>> res = new ArrayList<>();
​
    public List<List<Integer>> subsets(int[] nums) {
        backtrack(nums, new ArrayList<>(), 0);
        return res;
    }
​
    public void backtrack(int[] nums, List<Integer> current, int start) {
        // 当前路径本身就是一个合法子集
        res.add(new ArrayList<>(current));
​
        // 从 start 开始，依次尝试加入后面的元素
        for (int i = start; i < nums.length; i++) {
            current.add(nums[i]);              // 做选择
            backtrack(nums, current, i + 1);  // 递归到下一层
            current.remove(current.size() - 1); // 撤销选择
        }
    }
}

代码拆解

这段代码非常短，但它几乎把“组合型回溯”的核心结构完整体现出来了。 下面一步一步来看。

1. res 是做什么的？

List<List<Integer>> res = new ArrayList<>();

这是结果集，用来存放所有子集。

因为题目要求返回所有可能的子集，所以在回溯过程中，每形成一个合法子集，就要把它加入到 res 里。

2. subsets 函数在做什么？

public List<List<Integer>> subsets(int[] nums) {
    backtrack(nums, new ArrayList<>(), 0);
    return res;
}

这个函数做了两件事：

1. 从空路径开始回溯

2. 返回最终结果集

这里初始传入的是：

• 当前路径 current = []

• 起始位置 start = 0

这表示： 一开始什么都还没选，接下来可以从数组第 0 个位置开始选元素。

3. backtrack 里的参数分别表示什么？

public void backtrack(int[] nums, List<Integer> current, int start)

这三个参数非常关键：

• nums：原始数组

• current：当前已经选出来的子集

• start：接下来从哪个下标开始继续选

也就是说，这个函数表示的是：

当前已经得到一个子集 current，接下来可以从 start 位置开始，继续尝试把后面的元素加入进来。

只要把这个定义想清楚，整道题的递归结构就会非常自然。

4. 为什么一进递归就先把 current 加进结果集？

res.add(new ArrayList<>(current));

因为这道题和全排列不一样。 全排列要求必须选满所有元素之后，才能形成一个完整答案。

但子集题不是这样。

子集的特点是：

• 选 0 个元素也是合法子集

• 选 1 个元素也是合法子集

• 选 2 个元素也是合法子集

• …

• 全部选上也是合法子集

所以无论当前路径长度是多少，它本身都应该被视为一个答案。

这也是这道题和很多其他回溯题最不一样的地方：

不需要等到“递归到底”才收集答案，而是每一层的当前路径都可以收集。

注意这里一定要写：

new ArrayList<>(current)

因为 current 是一个会不断变化的路径对象，如果直接存引用，后面回溯时结果集内容会被修改掉。

5. 为什么循环从 start 开始？

for (int i = start; i < nums.length; i++)

这是整道题避免重复的关键。

假设当前已经选到了某个位置，那么下一步只允许从它后面的元素继续选。 这样就能保证子集中的元素顺序始终按原数组顺序递增。

例如对于数组 [1,2,3]：

• 生成 [1,2]

• 但不会再去生成 [2,1]

因为当已经选了 1 之后，下一步只允许从 2 和 3 开始选，不会回头再选 1 前面的元素。

这就是 start 的作用：

控制搜索只向后进行，从而避免重复。

6. 为什么递归时传的是 i + 1？

backtrack(nums, current, i + 1);

因为当前已经选了 nums[i]，下一层就不能再从 i 自己开始了，而应该从它后面的元素开始继续选。

这和“组合总和”不一样。

在组合总和里

一个数字可以重复使用，所以递归时传的是 i。

在子集这题里

每个元素在当前子集中只能出现一次，所以递归时应该传：

i + 1

也就是说：

选过当前位置后，下一层从后一个位置继续搜索。

7. 为什么最后要删除最后一个元素？

current.remove(current.size() - 1);

这是回溯的“撤销选择”步骤。

流程是这样的：

1. 先把某个元素加入当前路径

2. 递归进入下一层

3. 下一层搜索结束后，把刚才加进去的元素删除

4. 然后继续尝试别的元素

如果不执行这一步，那么当前分支的选择就会污染后面的分支，结果一定会出错。

所以这一步是回溯题的标准操作。

手动模拟一遍

我们用最经典的例子来走一遍：

nums = [1,2,3]

初始状态

调用：

backtrack(nums, [], 0)

当前路径是空集：

[]

先加入结果集。

当前答案：

[[]]

第一层循环：选 1

路径变成：

[1]

递归进入：

backtrack(nums, [1], 1)

先把 [1] 加入结果集。

当前答案：

[[], [1]]

第二层：在 [1] 的基础上选 2

路径变成：

[1,2]

递归进入：

backtrack(nums, [1,2], 2)

先把 [1,2] 加入结果集。

当前答案：

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

第三层：在 [1,2] 的基础上选 3

路径变成：

[1,2,3]

递归进入后，把它加入结果集：

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

然后没有更多元素可选，开始回退。

回到第二层：改选 3

在 [1] 的基础上，不选 2 的延伸分支结束后，再尝试选 3：

路径变成：

[1,3]

加入答案：

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

回到第一层：改选 2

路径变成：

[2]

继续往下会生成：

[2]
[2,3]

回到第一层：改选 3

路径变成：

[3]

最终会把所有子集都枚举出来。

最后答案就是：

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

顺序可能不同，但内容一定完整。

为什么总共有 2^n 个子集？

因为对于数组中的每一个元素，都有两种选择：

• 选

• 不选

如果数组长度是 n，那么总选择情况就是：

2 × 2 × 2 × ... × 2 = 2^n

所以一个长度为 n 的数组，总子集数量一定是：

2^n

这也是为什么这道题的结果集规模本身就是指数级的。

为什么这个方法是正确的？

因为这套回溯过程完整地枚举了所有可能的选法：

• 每次从当前位置开始，尝试选择一个元素

• 递归地继续决定后面元素选不选

• 同时用 start 保证搜索顺序固定，避免重复

这样做可以保证：

不会漏掉任何子集

因为每一种合法的“选元素组合”，都会在搜索树中对应一条路径。

不会产生重复子集

因为搜索过程始终只向后看，不会出现 [1,2] 和 [2,1] 这种顺序不同但本质相同的重复情况。

因此这个方法是完全正确的。

复杂度分析

时间复杂度

数组长度为 n 时，一共有：

2^n

个子集。

而每次把当前路径加入答案时，需要复制一份当前列表，最坏情况下复制长度可达 n。

所以总时间复杂度通常写作：

O(n * 2^n)

空间复杂度

递归深度最多为 n，当前路径长度也最多为 n，所以辅助空间复杂度为：

O(n)

如果把最终答案本身也算进去，那整体输出空间会更大，因为本身就有 2^n 个子集。

这道题真正想考什么？

这道题表面上是在求子集，但本质上非常适合训练“组合型回溯”的基本功。

第一，是否理解“当前路径本身就是答案”

很多人一开始学回溯时，会习惯于“只有走到底才加入答案”。 但子集题不是这样，它要求你意识到：

每一层的当前路径，都已经是一个合法解。

第二，是否理解 start 参数的意义

start 的作用不是随便传的，它本质上是在保证：

• 搜索只向后推进

• 不会产生重复组合

这是组合题、子集题里非常重要的模板思想。

第三，是否能区分排列题和子集题

• 排列题通常需要 used[]

• 子集 / 组合题通常需要 start

这两种模型虽然都属于回溯，但控制方式不一样。

和“全排列”有什么区别？

这两题特别容易放在一起对比。

全排列

要求的是顺序不同也算不同答案。 所以：

• 每一层都要从所有未使用元素里选

• 需要 used[] 数组

子集

不关心顺序，只关心选了哪些元素。 所以：

• 只需要从当前位置往后选

• 需要 start 参数

• 不需要 used[]

这就是两类回溯题最本质的区别之一。

总结

这道题的核心思想可以概括成一句话：

用回溯枚举所有可能的选择路径，并把每一层的当前路径都作为一个合法子集加入结果集。

具体步骤就是：

1. 用 current 表示当前子集

2. 每次进入递归时，先把当前子集加入结果

3. 然后从 start 开始枚举下一个可选元素

4. 选择一个元素加入路径

5. 递归进入下一层，并从 i + 1 开始继续搜索

6. 回溯时删除刚加入的元素，恢复现场

这样就能得到所有可能的子集。

这是一道非常经典、也非常值得反复理解的回溯题。 因为它会让你真正体会到：

• 回溯不只是“走到底才收答案”

• 很多组合型问题的关键是 start

• 子集问题的本质就是枚举所有选择情况

把这道题真正吃透之后，再去看：

• 子集 II

• 组合

• 组合总和

• 分割回文串

这些组合型回溯题时，你会明显更容易抓住套路。

因为“子集”本身就是回溯入门题里非常经典的一道模板题。