子集
Subsets
本机进度仅保存在当前浏览器
题目描述
给你一个整数数组 nums（元素互不相同），返回该数组所有可能的子集（幂集），解集不能包含重复的子集，顺序任意。
示例：nums = [1, 2, 3]，输出 [[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]。
解题思路
- 每个元素都有"选 / 不选"两种状态，全部 n 个元素的决定构成一棵深度为 n 的子集树，回溯就是这棵树的深度优先枚举。
- 常用实现：路径 path 记录已选元素，每次递归先把当前 path 存入结果，再从下一个下标开始继续选择。
- "从 start 开始"保证组合内部元素有序，天然去重；元素互不相同使问题无需剪枝。
参考实现
查看参考实现Python · 建议先自行作答
def subsets(nums):
res, path = [], []
def backtrack(start):
# 当前路径本身就是一个子集
res.append(path[:])
for i in range(start, len(nums)):
path.append(nums[i])
backtrack(i + 1)
path.pop()
backtrack(0)
return res