位运算 · 子集枚举

从 LC 78 子集出发，用 bit mask 枚举 2ⁿ 个子集，省去递归栈。

Medium预计阅读 45 分钟更新于 2026-05-18

1. 核心原理

子集枚举（subset enumeration） 指对一个有限集合 S = {a₀, a₁, …, aₙ₋₁}，按某种顺序遍历它的全部 2ⁿ 个子集或某个特定子族（如固定大小的子集、某个 mask 的子掩码）。这类操作出现在三种场景：组合 / 子集类输出题（LC 78 / 90）、状压 DP 的状态空间（LC 1986 / 698）、以及把"每个元素选 / 不选"的二值决策压成整数索引的题（LC 1255）。

把每个元素映射成一位 0/1 后，子集和 n 位整数 [0, 2ⁿ) 一一对应。"枚举所有子集"于是等价于"枚举所有 n 位整数"——递归 DFS 的栈帧被替换为整数下标，状态可以直接当数组键用。本节归纳子集枚举的三种循环骨架，它们的差别只在"循环条件"。

1.1 朴素做法的局限

第一反应是 DFS：对第 i 个元素递归"选 / 不选"，到 i == n 时把当前路径加入答案。时间 O(n × 2ⁿ)、空间 O(n × 2ⁿ) —— 与位运算解相同，没有渐进意义上的提升。但 DFS 写法有三个工程问题：

递归栈与 path 需要手动维护并回溯，错一行就会污染兄弟分支。
状态无法直接当索引：当 mask 既是答案又是 DP 状态时（如 dp[mask]），DFS 的 path 不是数组下标。
嵌套枚举难写：要"枚举一个 mask 的所有子掩码"时，DFS 需要传两个参数 + 双重回溯，远不如 for sub = mask; sub; sub = (sub - 1) & mask 干净。

1.2 关键洞察

子集与整数的双向映射有三条派生性质：

完整枚举：for mask in range(1 << n) 走过所有 2ⁿ 个子集，复杂度 O(2ⁿ)，循环本身没有递归栈。
子掩码枚举：sub = mask; while sub > 0: ...; sub = (sub - 1) & mask 走过 mask 的所有非空子集（不含 0）。对所有 mask 求和后的总迭代次数恰好是 O(3ⁿ)（§5.3 证明），这是子集 DP 跑得动 n ≤ 16 的核心。
固定 popcount 枚举：Gosper's hack（§5.4）从 (1 << k) - 1 起步，按字典序生成所有 popcount 等于 k 的 mask，总迭代次数 C(n, k) 而非 2ⁿ。

1.3 模板要素

子集枚举题的统一骨架由两件事组成：

三种循环条件：全子集 / 子掩码 / 固定 popcount，对应三种典型问题（输出全部、状压 DP 转移、限定大小）。
mask 到元素的翻译：for i in range(n): if mask >> i & 1: ...，把整数 mask 还原成参与子集的元素。这一步是 O(n)，所以单次"取出一个子集"的代价是 O(n)。

§2 给出三种循环的最小骨架代码。

1.4 套路类型一览

套路	循环条件	总迭代次数	适用场景 / 代表题
A 全子集	`for mask in range(1 << n)`	`2ⁿ`	枚举 `nums` 的所有子集（LC 78 / LC 90 / LC 1255）
B 子掩码	`sub = mask; while sub > 0: ...; sub = (sub - 1) & mask`	单 mask `2^popcount(mask)`，对全 mask 累计 `3ⁿ`	在 mask 内部枚举它的所有非空子集（子集 DP 内层，LC 1986 / LC 698 / LC 1681）
C 固定 popcount	Gosper's hack	`C(n, k)`	枚举所有恰有 `k` 个 1 的 mask（LC 1255 选 k 单词、LC 1494 选 k 课）

三者构成 A ⊃ B ⊃ C 的关系：

模板 A 枚举 0 ~ 2ⁿ − 1，等价于"枚举 (1 << n) − 1 这个全 1 mask 的所有子掩码"——是模板 B 取 mask = (1 << n) − 1 时的特例。
模板 C 是模板 A 的过滤：只保留 popcount(mask) == k 的 mask。直接写 for mask in range(1 << n): if popcount(mask) == k 也对，但常数大 C(n, k) / 2ⁿ 倍；当 k 远小于 n 时差距很大，Gosper's hack 直接跳到"下一个同 popcount 的 mask"省掉这个常数。

2. 通用模板

下面给出三种循环的最小骨架。前两个的循环条件本身只有一行差别——记忆点是「全子集用整数迭代，子掩码用 (sub - 1) & mask」。

# 模板 A：枚举 nums 的所有 2^n 个子集
def enumerate_all_subsets(nums: list[int]):
    n = len(nums)
    for mask in range(1 << n):                        # mask ∈ [0, 2^n)
        sub = [nums[i] for i in range(n) if mask >> i & 1]
        yield mask, sub

# 模板 B：枚举给定 mask 的所有非空子掩码
# 起点 sub = mask，每轮用 (sub - 1) & mask 跳到下一个
def enumerate_submasks(mask: int):
    sub = mask
    while sub > 0:
        yield sub
        sub = (sub - 1) & mask
    # 若需要包含空子掩码 0，循环结束后再 yield 一次

# 模板 C：Gosper's hack —— 枚举所有 n 位中恰有 k 个 1 的 mask
def enumerate_k_subsets(n: int, k: int):
    if k == 0:
        yield 0
        return
    x = (1 << k) - 1                                  # 起点：最低 k 位为 1
    limit = 1 << n
    while x < limit:
        yield x
        c = x & -x                                    # 取最低位的 1
        r = x + c                                     # 把那一段连续 1 进位
        x = (((r ^ x) >> 2) // c) | r                 # 把剩余 1 推回最低端

// 模板 A：枚举 nums 的所有 2^n 个子集
static void enumerateAllSubsets(int[] nums) {
    int n = nums.length;
    for (int mask = 0; mask < (1 << n); mask++) {
        List<Integer> sub = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            if (((mask >> i) & 1) == 1) sub.add(nums[i]);
        }
        // 使用 sub
    }
}

// 模板 B：枚举给定 mask 的所有非空子掩码
static void enumerateSubmasks(int mask) {
    for (int sub = mask; sub > 0; sub = (sub - 1) & mask) {
        // 使用 sub
    }
    // 若需空子掩码：循环结束后单独处理 sub = 0
}

// 模板 C：Gosper's hack —— 枚举所有 n 位中恰有 k 个 1 的 mask
static void enumerateKSubsets(int n, int k) {
    if (k == 0) { /* 处理空集 */ return; }
    int x = (1 << k) - 1;                             // 起点
    int limit = 1 << n;
    while (x < limit) {
        // 使用 x
        int c = x & -x;
        int r = x + c;
        x = (((r ^ x) >> 2) / c) | r;
    }
}

// 模板 A：枚举 nums 的所有 2^n 个子集
void enumerate_all_subsets(const vector<int>& nums) {
    int n = nums.size();
    for (int mask = 0; mask < (1 << n); mask++) {
        vector<int> sub;
        for (int i = 0; i < n; i++) {
            if ((mask >> i) & 1) sub.push_back(nums[i]);
        }
        // 使用 sub
    }
}

// 模板 B：枚举给定 mask 的所有非空子掩码
void enumerate_submasks(int mask) {
    for (int sub = mask; sub > 0; sub = (sub - 1) & mask) {
        // 使用 sub
    }
    // 若需空子掩码：循环结束后单独处理 sub = 0
}

// 模板 C：Gosper's hack —— 枚举所有 n 位中恰有 k 个 1 的 mask
void enumerate_k_subsets(int n, int k) {
    if (k == 0) { /* 处理空集 */ return; }
    int x = (1 << k) - 1;                             // 起点
    int limit = 1 << n;
    while (x < limit) {
        // 使用 x
        int c = x & -x;                               // 最低位的 1
        int r = x + c;                                // 把那段连续 1 进位
        x = (((r ^ x) >> 2) / c) | r;                 // 把剩余 1 推回最低端
    }
}

四点需要注意：

模板 B 不含空子掩码：循环条件 sub > 0，sub = 0 时退出。若题目需要空子集合法，在循环外补一次 sub = 0。
模板 B 的迭代顺序：(sub - 1) & mask 从大到小走子掩码（依字典序逆向）。对子集 DP 通常顺序无关；若需正序，外层再 reverse。
n 的上限：状压本身只在 n ≤ 20 可行（2²⁰ ≈ 10⁶），子集 DP（模板 B 双层）只在 n ≤ 16 可行（3¹⁶ ≈ 4 × 10⁷）。看到题面 n ≤ 14 / n ≤ 16 通常就是 bit mask 路线。
Gosper's hack 的 Python 版用 // 而非 /，因为 Python 的 / 是浮点除法。Java / C++ int 除法直接 / 即可。

3. 母题精讲

LeetCode 78. 子集

LC 78 子集：给一个不含重复元素的整数数组 nums，返回它所有可能的子集（幂集）。子集之间的顺序与子集内部的顺序都不限，但不能含重复的子集。

输入:  nums = [1, 2, 3]
输出:  [[], [1], [2], [3], [1,2], [1,3], [2,3], [1,2,3]]

数据范围：1 ≤ len(nums) ≤ 10，-10 ≤ nums[i] ≤ 10，所有元素互不相同。

3.1 第一反应：递归 DFS（每个元素选或不选）

n 个元素的幂集大小是 2ⁿ——每个元素都有"选 / 不选"两种状态，互相独立。最朴素的写法是 DFS 一棵深度 n 的二叉树：

class Solution:
    def subsets(self, nums: list[int]) -> list[list[int]]:
        n = len(nums)
        ans: list[list[int]] = []
        path: list[int] = []

        def dfs(i: int) -> None:
            if i == n:
                ans.append(path.copy())
                return
            # 不选 nums[i]
            dfs(i + 1)
            # 选 nums[i]
            path.append(nums[i])
            dfs(i + 1)
            path.pop()                   # 回溯

        dfs(0)
        return ans

时间 O(n × 2ⁿ)：递归树共 2ⁿ 个叶子，每个叶子拷贝长度最多 n 的 path。空间 O(n × 2ⁿ)：答案本身占这么大，再加上 O(n) 的递归栈与 path。

这份代码功能上完全对，也是「子集 / 组合 / 排列」三件套的常规打法。但在面试场景下还可以追问一句：

既然每个元素都是「选 / 不选」的独立二选一，把这 n 个选择拼成一个长度 n 的 0/1 串就能唯一编码一个子集——为什么我们要写 DFS、而不是直接枚举所有 0/1 串？

3.2 关键观察：子集 ↔ 长度 n 的 0/1 串 ↔ 一个 `n` 位整数

把 nums = [a, b, c]（n = 3）的 8 个子集列出来，并按下面的约定写成 0/1 串：第 i 位为 1 表示子集里包含 nums[i]。

mask    bit2 bit1 bit0    子集
000      0    0    0      []
001      0    0    1      [a]
010      0    1    0      [b]
011      0    1    1      [a, b]
100      1    0    0      [c]
101      1    0    1      [a, c]
110      1    1    0      [b, c]
111      1    1    1      [a, b, c]

整数 0 到 2ⁿ − 1 和 nums 的所有子集一一对应。所以「枚举所有子集」可以彻底改写成「枚举所有 n 位整数」，再把每个整数翻译回它对应的子集：

class Solution:
    def subsets(self, nums: list[int]) -> list[list[int]]:
        n = len(nums)
        ans: list[list[int]] = []
        for mask in range(1 << n):                  # 0 ~ 2ⁿ − 1
            sub = [nums[i] for i in range(n) if mask >> i & 1]
            ans.append(sub)
        return ans

时间 O(n × 2ⁿ)：外层 2ⁿ 次循环，内层把每个 mask 翻译成子集要扫 n 位。空间 O(n × 2ⁿ)，仍然由答案本身主导。

复杂度跟递归版本完全一样——两种写法都要枚举 2ⁿ 个子集、每个都要花 O(n) 来构造。但 bit 枚举有三个工程上的小优势：

没有递归。本题里两种写法的栈深都不是问题；但当题目把子集枚举嵌进 DP 里（§4.3），每个 mask 还要再嵌一层子掩码循环（O(3ⁿ)），递归写起来要传一堆状态参数、回溯也容易漏，两层 for 反而最干净。
状态紧凑。一个 int 就是一份完整的「选择记录」，可以直接当数组下标用——这是后面 dp[mask] 状压 DP 能成立的基础。DFS 的 path 是一个独立的 list，要换成等价的 mask 还得手动维护。
天然顺序。mask 从 0 到 2ⁿ − 1 单调递增，子集大小（popcount(mask)）不是单调的、但子集本身有一个稳定的「字典序」可以利用，做哈希 / 状压 / 记忆化都方便。

把这一观察推广，就能解决一族「需要枚举所有子集 / 所有 k 元子集 / 某个 mask 的所有子掩码」的题目。

4. 三道例题：LC 78 → 90 → 1986

下面按「无重复 → 有重复 → 嵌进 DP」的顺序展开。每道题都说明：「上一道的代码改哪里就能解这一道？为什么这一改改不动了？」

4.1 LC 78 子集（再贴一遍）

LC 78：给一个互不相同的整数数组 nums，返回它所有可能的子集。子集与子集内顺序均不限。

数据范围：1 ≤ len(nums) ≤ 10，-10 ≤ nums[i] ≤ 10，元素互不相同。

输入:  nums = [1, 2, 3]
输出:  [[], [1], [2], [3], [1,2], [1,3], [2,3], [1,2,3]]

解法：模板 A 直接套。

class Solution:
    def subsets(self, nums: list[int]) -> list[list[int]]:
        n = len(nums)
        ans: list[list[int]] = []
        for mask in range(1 << n):
            ans.append([nums[i] for i in range(n) if mask >> i & 1])
        return ans

逐段拆解：

外层 for mask in range(1 << n)：n 位整数遍历 0 到 2ⁿ − 1，对应 2ⁿ 个子集。
内层 mask >> i & 1：>> 在 & 之前结算，先把 mask 右移 i 位，再 & 1 取最低位——也就是 mask 的第 i 位。等价于 (mask >> i) & 1，但 Python 的运算符优先级允许省掉括号。
构造子集：第 i 位是 1 就把 nums[i] 加进去。Python 的列表推导式写起来最短，Java / C++ 要展成 for 循环。

复杂度：

时间 O(n × 2ⁿ)：外层 2ⁿ，内层每个 mask 检查 n 位。
空间 O(n × 2ⁿ)：答案本身的总元素数；不算返回值的话只有 O(n)（当前正在构造的子集）。

Follow-up（引出 LC 90）：现在 nums 里允许重复，结果集合里要求子集不重复。还能套这个 for 循环吗？

举个反例：nums = [1, 2, 2]，按模板 A 枚举出来的子集是

mask=000  []
mask=001  [1]
mask=010  [2]    ← 用了 nums[1]
mask=011  [1, 2]
mask=100  [2]    ← 用了 nums[2]，跟上面的 [2] 重复
mask=101  [1, 2] ← 跟 011 重复
mask=110  [2, 2]
mask=111  [1, 2, 2]

模板 A 把「位置」当成区分依据——nums[1] = 2 和 nums[2] = 2 是两个不同的 bit，所以它们生成的子集 [2] 是两条不同的记录，但题目要求把它们去重成一份。这就是 LC 90 的关键。

4.2 LC 90 子集 II

LC 90 子集 II：给一个可能含重复元素的整数数组 nums，返回所有不重复的子集。

数据范围：1 ≤ len(nums) ≤ 10，-10 ≤ nums[i] ≤ 10。允许重复值。

输入:  nums = [1, 2, 2]
输出:  [[], [1], [1,2], [1,2,2], [2], [2,2]]

思路：先排序，再用「相同值的 bitmask 必须是前缀 1」规则去重

把 nums 先升序排序，相同值就被聚到一起。对每一组相同值（设共有 c 个），合法的 mask 应该满足「这一组里被选中的位置是前 k 个（0 ≤ k ≤ c），不允许跳过」。

例如 nums = [1, 2, 2] 排序后 [1, 2, 2]，bit1 / bit2 都对应 2。「合法选法」只剩四种：

不选 2:        bit1=0, bit2=0
选 1 个 2:     bit1=1, bit2=0  ← 必须先选 bit1
选 2 个 2:     bit1=1, bit2=1

bit1=0, bit2=1（跳过第一个 2 直接选第二个）被禁止——它生成的子集 [2] 跟 bit1=1, bit2=0 完全一样。

把这条规则编进枚举里：对每个 mask，遍历每组相同值；如果发现这组里存在一个 0 位在某个 1 位之前（按数组下标顺序），就跳过这个 mask。

代码

class Solution:
    def subsetsWithDup(self, nums: list[int]) -> list[list[int]]:
        nums = sorted(nums)
        n = len(nums)
        ans: list[list[int]] = []
        for mask in range(1 << n):
            ok = True
            for i in range(1, n):
                # 同一组里：上一位没选、当前位选了 → 非法
                if nums[i] == nums[i - 1] and (mask >> i & 1) and not (mask >> (i - 1) & 1):
                    ok = False
                    break
            if ok:
                ans.append([nums[i] for i in range(n) if mask >> i & 1])
        return ans

逐段拆解：

nums = sorted(nums)：排序后相同值相邻，让「同一组」就是「相邻的同值段」。
for i in range(1, n)：检查相邻对 (i-1, i)。如果它们同值，并且 mask 在 i-1 位是 0、i 位是 1，那就是「跳过前一个 2 直接选后一个 2」的非法 mask，直接 break。
第二个列表推导式：mask 合法的话翻译成子集，逻辑跟 LC 78 一模一样。

也可以用哈希去重——把每个子集排序后转成 tuple，存进 set 里——但复杂度从 O(n × 2ⁿ) 退化到 O(n log n × 2ⁿ)（每个子集都要排序 + 哈希），写起来还更长。预排序 + bit 规则才是工业级写法。

复杂度：

时间 O(n × 2ⁿ)：外层 2ⁿ，内层 O(n) 检查 + O(n) 构造。
空间 O(n × 2ⁿ)：答案本身。

Follow-up（引出 LC 1986）：上面两题都是「枚举每个子集 + 输出」。如果子集本身只是中间状态、最终目标是某个最优值（比如「最少分多少组」「最大得分」），并且分组之间有递推关系，怎么办？

这就是子集 DP的入口：把 mask 当成 DP 状态，转移时从 mask 内部枚举子掩码。模板从 A 进化到 A + B 嵌套。

4.3 LC 1986 完成任务的最少工作时间段

LC 1986：给一个长度为 n 的正整数数组 tasks（tasks[i] 是第 i 个任务所需的小时数）和一个整数 sessionTime。你需要在若干个「工作时段」里完成所有任务，每个时段总时长不超过 sessionTime 小时，且任务不可拆分（一个任务只能整段塞进某一时段，不能跨时段）。返回最少需要多少个时段。

数据范围：1 ≤ len(tasks) ≤ 14，1 ≤ tasks[i] ≤ 10，max(tasks[i]) ≤ sessionTime ≤ 15。注意 n ≤ 14，所以 2ⁿ ≤ 2¹⁴ = 16384，状压完全跑得动。

输入:  tasks = [1, 2, 3], sessionTime = 3
输出:  2
解释:  时段 1 做 [1, 2]（总 3 小时），时段 2 做 [3]（总 3 小时）。

输入:  tasks = [3, 1, 3, 1, 1], sessionTime = 8
输出:  2
解释:  时段 1 做 [3, 3, 1]（总 7 小时），时段 2 做 [1, 1]（总 2 小时）。
       任务总时长 9 > 8，所以至少需要 2 个时段。

思路：状压 DP，外层全子集 + 内层子掩码枚举

把 mask（n 位）解读为「这一位为 1 的任务已经完成」。定义：

dp[mask] = 完成 mask 所有任务所需的最少时段数

转移：对 mask 来说，最后一个时段做了它的某个子集 sub（sub ⊆ mask）；这个子集必须能塞进一个时段（sum(tasks[i] for i in sub) ≤ sessionTime）。剩下的部分 mask ^ sub（mask 减去 sub）是更早完成的，对应 dp[mask ^ sub]。所以：

dp[mask] = min over all valid sub ⊆ mask of  dp[mask ^ sub] + 1

初始：dp[0] = 0（没有任务，零个时段）；所有非空 mask 初始为 +∞。

外层 for mask in range(1, 1 << n)，对每个 mask 用模板 B枚举所有非空子掩码 sub，预先判断 sub 是否合法（用时 ≤ sessionTime），合法就更新 dp[mask]。

优化：先把合法子掩码筛出来

对每个 mask 重新算一遍 sum(tasks[i] for i in sub) 太浪费——可以一次性预处理：对所有 sub（共 2ⁿ 个），计算 cost[sub] = sum，再把 valid[sub] = (cost[sub] <= sessionTime) 存下来。这里 cost 可以用递推：cost[sub] = cost[sub & (sub - 1)] + tasks[lowbit_index(sub)]，但直接两层 for 也不会超时（n ≤ 14）。

代码

class Solution:
    def minSessions(self, tasks: list[int], sessionTime: int) -> int:
        n = len(tasks)
        full = 1 << n

        # 1. 预处理：每个 mask 对应的任务总时长 + 是否能塞进一个时段
        cost = [0] * full
        for mask in range(1, full):
            low = mask & -mask                      # 最低位的 1
            idx = low.bit_length() - 1              # 它对应第几个任务
            cost[mask] = cost[mask ^ low] + tasks[idx]
        valid = [c <= sessionTime for c in cost]

        # 2. 子集 DP
        INF = n + 1                                 # n 个任务最差也就 n 个时段
        dp = [INF] * full
        dp[0] = 0
        for mask in range(1, full):
            sub = mask
            while sub > 0:
                if valid[sub]:
                    dp[mask] = min(dp[mask], dp[mask ^ sub] + 1)
                sub = (sub - 1) & mask
        return dp[full - 1]

逐段拆解：

预处理 cost：用递推 cost[mask] = cost[mask ^ low] + tasks[idx]——把 mask 最低位的 1 单独拆出来。mask & -mask 给出那一位本身（值为 2ᵏ），.bit_length() - 1 算出它在第几位。这是位运算章「lowbit + bit_length」组合的标准用法。
DP 主循环：外层 mask 从 1 到 full - 1，对每个 mask 内层用 (sub - 1) & mask 走过所有非空子掩码。
dp[mask] = min(dp[mask], dp[mask ^ sub] + 1)：尝试把 sub 作为最后一个时段，前 mask ^ sub 的最优值加 1。注意 mask ^ sub == mask − sub（因为 sub ⊆ mask），写哪个都行。
valid[sub] 跳过非法：不合法的 sub（超过 sessionTime）就别去更新，否则得到错误转移。

复杂度：

时间 O(3ⁿ)：外层 + 内层一共 Σ over mask of 2^popcount(mask) = 3ⁿ（§5.3 证明）。n = 14 时 3¹⁴ ≈ 4.8 × 10⁶，毫秒级。
空间 O(2ⁿ)：dp、cost、valid 三个长 2ⁿ 数组。

如果直接对每个 mask 暴力枚举所有 sub ⊆ {0..n-1}（不利用 sub ⊆ mask），就是 O(4ⁿ)——4¹⁴ ≈ 2.7 × 10⁸，会爆。模板 B 的 (sub - 1) & mask 是子集 DP 跑得动的核心。

到这里三道例题就连起来了：

LC 78 (无重复, 输出全子集)
  ↓ 加一句「同组前缀 1」规则
LC 90 (含重复, 输出去重子集)
  ↓ mask 从「答案」变成「DP 状态」, 内层换成子掩码
LC 1986 (子集 DP, 求最少时段)

5. 边界、易错与复杂度

5.1 `n` 的硬上限：Python 任意精度 vs Java / C++ 32 位

mask 要表示 2ⁿ 个状态。Python 的整数是任意精度，n = 60 也能算（但内层 2⁶⁰ 早就爆时间）。Java / C++ 用 int 是 32 位有符号，1 << 31 已经变成 Integer.MIN_VALUE、1 << 32 在 Java 里因为「shift 长度取低 5 位」直接退化成 1 << 0 = 1。

实际写题：

n ≤ 20：用 int。2²⁰ = 10⁶，循环也能跑得动。
n ≤ 30：必须用 long / int64；1L << 30 在 Java 里安全，1 << 30 也是合法 int。
n > 30：状压本身已经不可行（2³⁰ 是 10⁹，循环跑不过），需要换算法。

Python 上写 for mask in range(1 << n) 不会溢出，但 n 超过 20 的时候 2ⁿ 本身就是性能问题——2²⁵ = 3 × 10⁷，单层循环 OK，但内层再嵌一层子掩码就 3²⁵ ≈ 10¹²，根本跑不动。

5.2 `mask >> i & 1` 的运算符优先级

Python / Java / C++ 里运算符优先级几乎都一样：>> 比 & 紧。所以 mask >> i & 1 = (mask >> i) & 1，不是 mask >> (i & 1)。三种语言这一点是一致的，写题时不用括号也没问题。

但 == 比 & 紧——x & 1 == 1 在 Python 里是 x & (1 == 1) = x & True = x & 1，正好歪打正着；但在 Java / C++ 里 (x & 1) == 1 才是想要的写法，不要省括号。这是位运算的经典坑。

5.3 子掩码枚举为什么是 `O(3ⁿ)` 而不是 `O(4ⁿ)`

外层 mask 枚举 2ⁿ 个值；对每个 mask，内层用 (sub - 1) & mask 枚举它的所有 2^popcount(mask) 个子集。总操作数：

Σ over mask from 0 to 2ⁿ−1 of 2^popcount(mask)
= Σ over k from 0 to n of C(n, k) × 2^k
= (1 + 2)ⁿ                  (二项式定理)
= 3ⁿ

直观解释：每一位有三种可能——「不在 mask 里」「在 mask 里、不在 sub 里」「在 mask 里、在 sub 里」。n 位独立 → 总状态数 3ⁿ。

n = 16 时 3¹⁶ ≈ 4.3 × 10⁷，毫秒级。这是子集 DP 能处理 n ≤ 16 的根本原因。

5.4 Gosper's hack 的推导（选读）

模板 C 一行 x = (((r ^ x) >> 2) / c) | r 看起来像魔法。设 x 是当前的 mask，要找下一个同 popcount 的 mask x_next：

c = x & -x：取 x 最低位的 1（这是个 2 的幂）。
r = x + c：把 x 最低端的一段连续 1 整段进位掉——这段连续 1 变 0，再往上一位 +1。例如 x = 0b 00111100，c = 0b 00000100，r = 0b 01000000。
r ^ x：找出 r 和 x 不同的那些位——就是「被进位影响的整段」。继续上例：r ^ x = 0b 01111100。
(r ^ x) >> 2：右移 2 位，把这段「向左挪了一位的 1」推回到最低端，并比原来短一位（少了一个 1，因为最低位被进位吃掉了）。继续上例：0b 00011111。
... / c：除以 c（也就是右移 log₂ c 位），把这段 1 推到位置 0。继续上例：c = 4，0b 00011111 / 4 = 0b 00000111。
| r：把这段补回 r 上。继续上例：r | 0b 00000111 = 0b 01000111，这就是下一个同 popcount 的 mask。

整体保证了「popcount 不变」+「字典序严格递增」。停止条件 x < limit = 1 << n 等价于「最高位还没超过 n 范围」。

Python 因为是任意精度整数，/ 必须改成整除 //；Java / C++ 用 int 除法即可。

5.5 复杂度速查

题	算法	时间	空间
LC 78	模板 A	`O(n × 2ⁿ)`	`O(n × 2ⁿ)` 答案
LC 90	A + 同组前缀 1 规则	`O(n × 2ⁿ)`	`O(n × 2ⁿ)` 答案
LC 1986	A + B（子集 DP）	`O(3ⁿ)`	`O(2ⁿ)`
LC 698 / 1494 / 2305	子集 DP 变体	`O(3ⁿ)` 或 `O(n × 2ⁿ)`	`O(2ⁿ)`
LC 1255 / 1681	含「枚举 k 元 / 不相交对」的状压	`O(3ⁿ)` 或更精细	`O(2ⁿ)`

「状压能处理 n ≤ 20、子集 DP 能处理 n ≤ 16」是这一族题的固定上限。看到 n ≤ 14 / n ≤ 16，几乎肯定要走 bit mask 路线。

6. 大厂真题作业

Pro 会员

解锁完整北美 OA 题库

165 家公司 / 1000+ 道真题 · Python · Java · C++ 三语题解 · 月度更新

开通会员已是会员，去登录

7. 小结

子集枚举就一句话：「n 个独立的选 / 不选 ↔ n 位整数 0 ~ 2ⁿ − 1」。模板 A 直接覆盖 LC 78 / 90，模板 B 把它升级到「mask 内部再枚举子掩码」做子集 DP（O(3ⁿ)），模板 C Gosper's hack 处理「限定 popcount」的场景。n ≤ 14 ~ 16 是状压的硬上限，看到这个数据范围基本可以条件反射地走 bit mask。

位运算 · 子集枚举

解锁完整北美 OA 题库

On this page