LeetCode 78中等回溯
子集 图解题解
这道题到底在问什么
返回数组(元素互不相同)的所有子集(幂集)，不能有重复。
- nums
- [1, 2, 3]
- 输出
- [], [1], [2], [3], [1,2], [1,3], [2,3], [1,2,3]
先想最直接的笨办法
子集数量本来就是 2ⁿ，躲不开。关键是咋系统地枚举，既不漏掉，也不会出现 [1,2] 和 [2,1] 这种重复。（动画第 3 步）
最优解：一步一步想明白
- 3子集数量本来就是 2ⁿ，躲不开。关键是咋系统地枚举，既不漏掉，也不会出现 [1,2] 和 [2,1] 这种重复。
- 4从空集出发，每走到一个节点就把当前 path 记为一个子集；然后只从「上次选的位置之后」继续选下一个数（start 索引），这样保证每个子集元素递增、绝不重复。选完撤销，回头试别的。
- 5path=[] → res 加 []一开始 path 空，先把空集 [] 记进结果——它也是一个合法子集。
- 6path=[1]选 1，path=[1]，立刻记录。接下来只能从 1 后面（2、3）里选。
- 7path=[1,2]在 [1] 基础上选 2，path=[1,2]，记录。继续只能往后选 3。
- 8path=[1,2,3]再选 3，path=[1,2,3]，记录。后面没数可选了，这条路走到底，开始回溯。
- 9path=[1,3]撤销 3、撤销 2，回到 [1]。这次跳过 2 直接选 3，得到 [1,3] 并记录。
- 10path=[2]彻底撤回到空，从 2 开头：path=[2] 记录。注意不会再选 1（start 在 2 后面），所以不会出现 [2,1]。
- 11path=[2,3]在 [2] 后选 3，得 [2,3] 记录。
- 12path=[3]回到根，从 3 开头：[3]。8 个子集全部集齐，结束。
- 15回溯就是在决策树上 DFS：进入一个分支前「做选择」、退出时「撤销选择」。子集、组合、排列、分割都是它。
- 20把这题练到能复述后，再去同类题里迁移：先复用状态定义，再调整边界条件。
⚠️ 容易写错的地方
✗ 错：res.append(path)
✓ 对：res.append(path[:]) 存副本
path 后面会变，直接存会被改掉
✗ 错：不用 start，每次从 0 选
✓ 对：从 start 开始选
否则出现 [1,2] 和 [2,1] 重复
完整代码（Python / C++ / Java）
Python
class Solution:
def subsets(self, nums):
ans = []
def backtrack(start, path):
ans.append(path[:])
for i in range(start, len(nums)):
path.append(nums[i])
backtrack(i + 1, path)
path.pop()
backtrack(0, [])
return ansC++
class Solution {
public:
vector<vector<int>> ans;
vector<int> path;
void backtrack(vector<int>& nums, int start) {
ans.push_back(path); // 每个节点都收集
for (int i = start; i < nums.size(); i++) {
path.push_back(nums[i]); // ① 选
backtrack(nums, i + 1); // ② 递归 i+1（不回头）
path.pop_back(); // ③ 撤销
}
}
vector<vector<int>> subsets(vector<int>& nums) {
backtrack(nums, 0);
return ans;
}
};Java
class Solution {
List<List<Integer>> ans = new ArrayList<>();
List<Integer> path = new ArrayList<>();
void backtrack(int[] nums, int start) {
ans.add(new ArrayList<>(path)); // 每个节点都收集
for (int i = start; i < nums.length; i++) {
path.add(nums[i]); // ① 选
backtrack(nums, i + 1); // ② 递归 i+1
path.remove(path.size() - 1); // ③ 撤销
}
}
public List<List<Integer>> subsets(int[] nums) {
backtrack(nums, 0);
return ans;
}
}套路模板 · 回溯三件套（背下来）
def backtrack(start, path):
if 满足结束条件: res.append(path[:]); return # 或每节点都收集
for i in range(start, n):
path.append(choices[i]) # ① 选
backtrack(i + 1, path) # ② 递归(i+1去重/i可复用)
path.pop() # ③ 撤销void backtrack(int start, vector<int>& path) {
res.push_back(path); // 子集:每个节点都收集
for (int i = start; i < n; i++) {
path.push_back(choices[i]); // ① 选
backtrack(i + 1, path); // ② 递归(i+1 不回头)
path.pop_back(); // ③ 撤销
}
}void backtrack(int start, List<Integer> path) {
res.add(new ArrayList<>(path)); // 子集:每个节点都收集
for (int i = start; i < n; i++) {
path.add(choices[i]); // ① 选
backtrack(i + 1, path); // ② 递归(i+1 不回头)
path.remove(path.size() - 1); // ③ 撤销
}
}复杂度
时间复杂度
O(n · 2ⁿ)
2ⁿ 个子集，每个复制 O(n)
空间复杂度
O(n)
递归深度 + path
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 子集 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
回溯三件套是什么？+
① 做选择(选/不选当前元素) ② 递归下一层 ③ 撤销选择(回溯)。
子集 / 组合 / 排列的区别？+
子集=每个选不选 2^n；组合=选 k 个 C(n,k)；排列=顺序也算 n!。框架都是回溯，差在分支与 start。
有重复元素(LC90)怎么去重？+
先排序，同一层跳过相邻相同值(i>start && nums[i]==nums[i-1])。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。