Meta Subsets：包含/不包含扩展与输出下界

题意与假设

这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。

• 训练values互异、hashable，输出子集value列表，保持原输入相对顺序；包含空集，不修改输入。重复值版本需另定去重合同。

解题路线

1. 初始result=[[]]，处理新value时，把处理前已有每个subset加上value复制进result，原subset代表不选value，新subset代表选。
2. 归纳：每个子集唯一分为包含当前value/不含两类，旧集合正确且两类不重复，因此每轮结果恰好所有已处理元素子集。
3. 循环上界range(len(result))在扩展前固定，不能一边遍历可增长list一边无限追加。每个新subset必须新list，不能把同一个可变对象多次放入结果。
4. 生成顺序不是按长度/字典序，题面若要求排序还需额外成本；只求数量可直接2^N而不生成所有列表。

手动走一遍

[a,b]生成[]、[a]、[b]、[a,b]；空输入结果[[]]不是[]。输入[a,a]当前拒绝，不能输出重复值子集再称unique。

Python 参考实现

下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。

代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。

def subsets(values):
    """Distinct hashable values; [] included; no input mutation."""
    if len(set(values))!=len(values):raise ValueError('distinct values required')
    result=[[]]
    for value in values:
        for i in range(len(result)):result.append(result[i]+[value])
    return result

复杂度

子集数2^N，总元素出现N·2^(N−1)，显式输出时间/空间O(N2^N)不可避免；若只递归yield，辅助可O(N)但调用方收集仍同输出成本。

易错点与追问

容易失分的边界

• 空集遗漏。
• 遍历增长中的result导致追加循环失控。
• 重复输入未定去重，却按2^N当unique value subsets。

继续深挖

• 重复值版本可排序并同层跳重复，如何证明不漏？
• 只能输出大小K子集时，组合数量C(N,K)和输出成本怎样算？