78. 子集 (Medium)
专题归类： 08-回溯算法 LeetCode 链接： https://leetcode.cn/problems/subsets/
在线做题： 写 Python 代码并运行 · Java 跳转 LeetCode
题目描述
给你一个整数数组 nums，数组中的元素互不相同。返回该数组所有可能的子集（幂集）。
解集不能包含重复的子集。你可以按任意顺序返回解集。
示例 1：
输入：nums = [1,2,3]
输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
示例 2：
输入：nums = [0]
输出：[[],[0]]
提示：
1 <= nums.length <= 10-10 <= nums[i] <= 10nums中的所有元素互不相同
题目详细分析
数据范围含义：
nums.length <= 10：规模很小，2^10 = 1024，全部枚举完全可行。这暗示可以使用回溯或位运算。- 所有元素互不相同：简化了问题，不需要考虑重复元素带来的去重问题（如有重复参见 90-子集 II）。
核心约束：
- 子集不关心元素顺序，
[1,2]和[2,1]被视为同一个子集。 - 空集是任何集合的子集，必须包含在结果中。
- 每个元素有”选”和”不选”两种状态。
与排列的区别：
- 排列关注顺序，子集不关注顺序。
- 排列选满 n 个元素才记录，子集每一步都可以记录。
- 排列用 visited 控制，子集用 start 控制。
小白版直白理解
就像你面前有 n 种水果（苹果、香蕉、橘子），你要做成水果拼盘。你可以不放任何水果（空盘），也可以只放苹果，或只放香蕉，或放苹果+香蕉……总之，每种水果只有”放”或”不放”两种选择。所有可能的拼盘组合就是子集。
换个比喻：你要从衣橱里挑衣服出门，每件衣服都可以选择”穿”或”不穿”，所有可能的穿衣搭配方案就是子集。
解题思路
思路一：回溯 + start 参数（推荐）
核心思想： 与全排列不同，子集不关心顺序。使用 start 参数控制每次只能从当前索引之后的元素中选择，避免产生重复组合。
关键洞察： 排列在叶子节点记录，而子集在每个节点都记录。因为 [1]、[2]、[1,2] 都是子集，中间状态也要加入结果。
决策树可视化（以 [1,2,3] 为例）：
[]
/ | \
[1] [2] [3]
/ \ |
[1,2] [1,3] [2,3]
|
[1,2,3]
每个节点（包括根节点）都加入结果。
def subsets(nums):
res = []
n = len(nums)
def backtrack(start, path):
# 每个节点都加入结果（包括空集）
res.append(path[:])
# 从 start 开始，避免重复
for i in range(start, n):
path.append(nums[i]) # 做选择
backtrack(i + 1, path) # 递归：只能选 i 之后的元素
path.pop() # 撤销选择
backtrack(0, [])
return res思路二：位运算法
核心思想： n 个元素，每个元素可选可不选，恰好对应二进制位 0/1。2^n 种状态映射所有子集。
以 [1,2,3] 为例，3 位二进制数：
000 → [] 100 → [1]
001 → [3] 101 → [1,3]
010 → [2] 110 → [1,2]
011 → [2,3] 111 → [1,2,3]
def subsets(nums):
n = len(nums)
res = []
# 从 0 到 2^n - 1 枚举所有状态
for mask in range(1 << n):
subset = []
for i in range(n):
if mask & (1 << i): # 第 i 位为 1 表示选中 nums[i]
subset.append(nums[i])
res.append(subset)
return res时间复杂度： O(n x 2
思路三：迭代法（动态增量）
核心思想： 每处理一个新元素，就在已有所有子集的基础上追加这个元素，形成新子集。
初始：[[]]
处理 1：[[], [1]]
处理 2：[[], [1], [2], [1,2]]
处理 3：[[], [1], [2], [1,2], [3], [1,3], [2,3], [1,2,3]]
def subsets(nums):
res = [[]]
for num in nums:
# 对当前所有子集，追加新元素
for i in range(len(res)):
res.append(res[i] + [num])
return res易错点
start参数传递错误：递归时应该传i + 1而不是start + 1。start + 1会导致元素被跳过或重复访问。- 忘记创建副本：
res.append(path[:])而不是res.append(path)。path随后会被修改，不创建副本会导致结果被覆盖。 - 空集遗漏：空集是任何集合的子集，必须加入结果。回溯法在首次调用时就加入空集。
- 与排列混淆：子集用 start 控制方向避免重复，排列用 visited 从全部元素中选择，这两者容易混淆。
框架提炼
子集/组合问题的回溯模板：
def backtrack(start, path):
# 每个节点都记录结果（区别于排列只在叶子节点记录）
res.append(path[:])
for i in range(start, n):
path.append(nums[i]) # 做选择
backtrack(i + 1, path) # 递归：只能向后选
path.pop() # 撤销选择“选或不选”的思维模型：
- 回溯视角：从空集开始，逐个决定每个元素”加入/不加入”。
- 位运算视角：n 位二进制数，0 表示不选，1 表示选。
- 迭代视角：新元素加入已有所有子集，规模翻倍。
注意事项：
- 组合问题（如 77-组合）只需在特定长度时记录，其他与子集完全一致。