Subsets
你会得到一个由互不相同的整数构成的列表 nums。返回它的所有子集，包括空集和完整列表，因此 n 个值会得到 2^n 个子集。每个子集中的值都按升序排列，子集也按字典序排列：逐个比较两个子集中的值，第一个不同的值决定顺序；如果一个子集是另一个子集的开头，则较短的子集排在前面。对于 [1, 2]，答案是 [[], [1], [1, 2], [2]]。
函数
- numsinteger-array
- 所有值都各不相同，顺序任意
- 返回值integer-2d-array
- 每个子集都按升序排列，并按字典序列出
约束条件
1 ≤ nums.length ≤ 10-10 ≤ nums[i] ≤ 10-
nums中的所有值都不同。 nums的顺序可以是任意的。
示例
- 输入
- nums = [3, 1, 2]
- 输出
- [[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]
- 解释
- 三个值会产生 2^3 = 8 个子集。
[1, 2]排在[1, 2, 3]前面，因为它是后者的开头；而[1, 2, 3]排在[1, 3]前面，因为在第二个位置上，2 小于 3。
- 输入
- nums = [0]
- 输出
- [[], [0]]
- 解释
- 一个值有两个子集：不选它，得到
[]；选它，得到[0]。空子集始终排在最前面。
- 输入
- nums = [5, -2]
- 输出
- [[], [-2], [-2, 5], [5]]
- 解释
- 这些值排序后是 -2 和 5，所以按这个顺序写成
[-2, 5]。包含 -2 的每个子集都排在[5]前面，因为 -2 小于 5。
进阶
你能不使用递归，直接根据前一个子集构建每个子集，生成相同的列表吗？
提示
逐个打开提示，每个都会多透露一点。
子集中，每个值只有两种可能：包含或不包含。一个包含
n个值的列表有多少个子集？你可以怎样从较小的子集构建出每一个子集？先对这些值进行排序。如果你每次只添加位于上一个添加值右侧的值，那么每个子集都会按升序构建，而且不会重复构建任何子集。
编写一个接收起始索引的递归辅助函数。它会将当前路径记录为一个子集，然后从起始索引开始遍历到末尾，为每个索引对应的值，将其添加到路径中，再从下一个索引开始递归，最后再移除该值。在进入循环前记录路径，这样生成的子集就会按字典序排列，无需排序。
题解
共有 2^n 个子集，因此没有任何方法能将工作量降到 O(2^n) 以下。真正的问题是，如何按要求的顺序生成每个子集，且只生成一次，而不必事后对 1024 个列表进行排序。按排序后的值进行回溯，并在进入决策树的每个节点时记录该节点，就能按字典序遍历所有子集。
位掩码，然后排序
思路
将排序后的值依次放在位置 0 到 n-1。一个数的 n 个比特表示每个位置是否选中，因此 0 到 2^n-1 这些数恰好各对应一个子集：对于 [1, 2, 3]，掩码 5 的二进制表示是 101，对应 [1, 3]。从位置 0 开始读取比特，就能按升序写出每个子集。
这些掩码的顺序不对：掩码 2 对应 [2]，掩码 3 对应 [1, 2]，所以 [2] 会排在 [1, 2] 前面。按值逐个比较，并将前缀排在前面的排序方式可以解决这个问题。这种排序大约需要 n × 2^n 次比较，每次最多比较 n 个值；当 n = 10 时，大约要读取 10^5 次，而回溯算法完全不需要做这些工作。
算法
- 对
nums排序，使每个子集都按升序排列。 - 对于从 0 到 2^n-1 的每个掩码，收集对应位为 1 的位置上的值。
- 对这些子集组成的列表排序：从两个子集第一个不同的位置开始，值较小的排在前面；如果其中一个先结束，则它排在前面。
- 返回排序后的列表。
def subsets(nums):
values = sorted(nums)
n = len(values)
result = []
for mask in range(1 << n):
# Bit i of mask says whether values[i] is in this subset.
result.append([values[i] for i in range(n) if (mask >> i) & 1])
# Python compares lists position by position, and a prefix comes first.
result.sort()
return result回溯：选择、探索、撤销选择
思路
把这些子集想象成一棵树。根节点是空子集，在一个节点下方，你可以添加任何大于其中最后一个值的值：对于 [1, 2, 3]，[1] 的子节点是 [1, 2] 和 [1, 3]。每个子集只会出现一次，因为它只有一种升序写法，而且每个节点都是一个答案，包括内部节点。
回溯使用一个共享列表 path 遍历这棵树，并在到达每个节点时记录它的副本。这样每个父节点都会排在它的子节点之前，并且从最小值开始尝试子节点，会先完成一条分支，再处理下一条：无需排序即可得到字典序。
这棵树有 2^n 个节点，每次复制的成本最多为 n：O(n × 2^n)，即答案的大小；此外，路径和调用栈需要 O(n) 空间。
算法
- 将这些值排序。
- 编写
explore(start)。它会先将path的副本追加到结果中。 - 然后，对于从
start到末尾的每个索引i：将values[i]追加到path中（选择），调用explore(i+1)（探索），再移除最后一个值（撤销选择）。 - 使用空路径调用
explore(0)，并返回结果。
def subsets(nums):
values = sorted(nums)
result = []
path = []
def explore(start):
# Every node of the decision tree is a subset: record it on the way in.
result.append(path[:])
for i in range(start, len(values)):
path.append(values[i]) # choose
explore(i + 1) # explore: only larger values may follow
path.pop() # un-choose
explore(0)
return result
易错点和边界情况
- 追加的是
path本身，而不是它的副本。这样，每个条目都会指向同一个列表；遍历结束时该列表为空，所以最终会返回 2^n 个[]的副本。 - 忘记对
nums排序。对于[3, 1, 2]，构建出的树会包含[3, 1]，这不是升序排列。 - 像排列问题那样只在叶节点记录结果。每个节点都是一个子集，所以返回的结果太少。
- 递归时使用
start+1，而不是i+1。这样，一个值后面就可能跟着更大的值或它本身，生成[3, 2]和[1, 3, 3]这样的列表。 - 记录包含或排除树的叶节点。这样能找到全部 2^n 个子集，但先包含会把完整列表放在最前面，先排除则会把
[3]放在[2]前面。
常见问题3
一个含有 n 个元素的集合有多少个子集？
2^n。每个元素都可以独立地选择是否包含，因此选择数会相乘。3 个值会产生 8 个子集，10 个值会产生 1024 个子集，其中包括空子集和全集。
子集问题的时间复杂度是多少？
O(n × 2^n)。一共有 2^n 个子集，写出一个子集最多需要 n 步，因此仅返回答案就需要这么多时间。回溯法达到这个时间复杂度，额外空间复杂度为 O(n)；使用位掩码后再排序，会额外增加一个 n 的因子。
如何处理 Subsets 中的重复值？
对值进行排序，然后在辅助函数的循环中，跳过与同一层中前一个值相等的值：i > start 和 values[i] == values[i-1]。第一个副本已经探索了所有使用它的子集，因此从第二个副本开始的分支会重新构建相同的子集。
相似题目
运用相同思路的题目。做两三道，才能真正掌握一种模式。
def subsets(nums):
# 在这里编写代码测试 #1
测试 #2
测试 #3
参数
nums = [3, 1, 2]
预期输出
[[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]