子集枚举

What · 是什么

子集枚举：给定掩码 m，枚举它的所有子掩码 s（s 的每一位都在 m 中）。核心代码：`s=m; while True: use(s); if s==0: break; s=(s-1)&m`，按子掩码从大到小遍历，每个 O(1)。配合外层枚举所有掩码 m，总复杂度 O(3^n)（因为对每个元素有三种状态：不在 m、在 m 不在 s、在 m 且在 s）。子集 DP（状压 DP，如集合覆盖、旅行商、图论划分）大量使用。

Why · 为什么

How · 实现

伪代码

# 枚举 m 的所有子掩码（含 m，不含 0 除非额外处理）
def submasks(m):
    s = m
    while True:
        yield s
        if s == 0:
            break
        s = (s - 1) & m

# O(3^n)：所有掩码的所有子掩码
for m in range(1 << n):
    for s in submasks(m):
        ...

Python 实现

def submasks(m):
    s = m
    while True:
        yield s
        if s == 0:
            break
        s = (s - 1) & m


def main():
    # 子掩码完整性与有序性
    got = list(submasks(0b101))  # 5
    assert got == [0b101, 0b100, 0b001, 0], got
    assert sorted(got) == sorted([0b101, 0b100, 0b001, 0])
    # 数量 = 2^popcount(m)
    m = 0b1101
    lst = list(submasks(m))
    assert len(lst) == (1 << m.bit_count())
    # 每个子掩码都确实是 m 的子集
    for s in lst:
        assert (s & m) == s
        assert (s | m) == m
    # 全部元素只出现一次（无重复）
    assert len(set(lst)) == len(lst)
    # O(3^n) 规模验证：n=12 时总次数
    n = 12
    total = 0
    for mm in range(1 << n):
        for _ in submasks(mm):
            total += 1
    assert total == 3**n, (total, 3**n)
    # 经典子集 DP 小例：集合覆盖成本最小化（伪应用）
    # 把 {0,1,2} 划分成若干子集，成本=子集大小，求最小总成本覆盖全集
    full = (1 << 3) - 1
    INF = 10**9
    dp = [INF] * (1 << 3)
    dp[0] = 0
    for m in range(1, 1 << 3):
        # 枚举子集做划分：任选一个子集 s，成本 = popcount(s)，合并剩余
        for s in submasks(m):
            if s == 0:
                continue
            rem = m & ~s
            dp[m] = min(dp[m], dp[rem] + s.bit_count())
    assert dp[full] == 3  # 分成3个单元素
    print("submask-enum OK")


if __name__ == "__main__":
    main()

易错点

• 循环必须处理 s==0 的退出，否则 s=(0-1)&m = m 死循环
• yield 生成器在超高频调用（3^n 规模）有开销，性能瓶颈时改内联 while
• 子掩码按数值递减，不要假设与按大小递增一致
• 子集 DP 中 rem = m & ~s 而非 m^s（语义等价但显式掩码更清晰），注意 ~s 在 Python 是无限位宽取反，&m 后安全
• 忘记 m 本身也是其子掩码（含全集）；空集 0 也是子掩码（通常单独处理）
• 3^n 复杂度对 n≥19 会超时，误估 n 上限

例题

信源

• CP-Algorithms✓ https://cp-algorithms.com/algebra/all-submasks.html
• cph✓ https://usaco.guide/CPH.pdf#page=105