题目重点：给数组返回所有子集；说明空集、重复元素时的同层跳过、指数输出下界与递归回退。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 训练版输入可能含重复数值，返回按元素多重集区分的唯一子集；每个子集内部升序，整体 DFS 顺序。
- 若题目把相同值但不同下标当不同子集，则不应去重，输出可达 2^n。
解题路线
- 先排序，让相同值相邻；每个递归调用先记录当前 path 作为一个子集，包括根的空集。
- 从 start 起枚举下个元素，若 i>start 且 a[i]==a[i−1]，跳过同一层的重复首选；进入下一层后允许再选相同值。
- 回溯后 pop，确保分支之间互不污染；用 [1,2,2] 手推 6 个不同子集。
- 解释输出本身可能指数级，不存在把全部结果写出仍为 O(n) 的算法。
手动走一遍
[1,2,2] 的唯一子集是 [],[1],[1,2],[1,2,2],[2],[2,2]；第二个 2 在根层被跳过，但在第一个 2 之后可以选入。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
def distinct_subsets(values):
"""Return distinct subsets of a multiset, including the empty subset."""
ordered = sorted(values)
result = []
current = []
def visit(start):
result.append(current.copy())
for i in range(start, len(ordered)):
if i > start and ordered[i] == ordered[i - 1]:
continue
current.append(ordered[i])
visit(i + 1)
current.pop()
visit(0)
return result
复杂度
排序 O(n log n)；最多 2^n 个子集，逐项复制路径的总时间/输出空间 O(n·2^n)，递归额外 O(n)。
易错点与追问
容易失分的边界
- 全局跳过重复值导致 [2,2] 消失。
- 记录同一个可变 path 引用而非复制。
- 忘记空集。
- 把指数输出成本说成线性。
继续深挖
- 若只需子集数？
- 如何惰性生成避免一次存全部？
- 若要固定大小 k 的子集怎么剪枝？
