题目重点：按值多重集合输出不同子集，重复位置不重复返回相同值组合。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 输入可重复可排序，输出列表中子集内非降；空子集只一份。
- 如果要求按位置输出，两个相同数仍可构成不同选择，本去重合同不同。
解题路线
- 排序使同值连续。不同于前一值时对所有现有子集附加当前；相同值时只扩展上一轮新增的子集。
- 例如第二个2只扩展第一次2创建的带2子集，从而生成两个2的组合，不再重新生成单个2。previous_start保存上一轮扩展前的size。
- 每个子集由各值选0..frequency次唯一决定；方法每轮只新增该值次数更高的层，完整且无重。
手动走一遍
[1,2,2]返回[],[1],[2],[1,2],[2,2],[1,2,2]共6种。n个互不同数输出2^n；同一值重复n次只有n+1种，但列表复制成本仍依总输出元素数。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
def subsets(a):
a=sorted(a)
result=[[]]
previous_start=0
for i,x in enumerate(a):
size=len(result)
start=previous_start if i and a[i-1]==x else 0
result.extend(result[j]+[x] for j in range(start,size))
previous_start=size
return result
复杂度
排序O(nlogn)；输出子集数量S=Π(c_v+1)，时间/空间至少Ω(Σsubset长度)，最坏O(n2^n)。不能简单声称O(n)。
易错点与追问
容易失分的边界
- 先生成全部位置子集再set去重会浪费指数重复工作。
- 原地遍历不断增长的result可能无限扩展，必须固定旧size。
继续深挖
- 只迭代不同时存全部结果，怎样用计数向量回溯？
- 输出按子集总和排序为什么不能直接沿当前构造顺序？
