算法刷题系列（六）：二进制枚举——遍历集合的所有子集

算法刷题系列（六）：二进制枚举——遍历集合的所有子集

上一篇介绍了如何用一个二进制掩码表示一组开关状态。本篇进一步利用这个表示方法：给定 n 个元素，每个元素都可以选或不选，因此所有选择方案都能用 0 到 2^n - 1 之间的整数表示。

我们将用一个自创的背包容量检查例子，枚举所有物品子集，并筛选总重量不超过容量的方案。重点是理解“掩码如何对应子集”、算法复杂度为何呈指数增长，以及什么时候适合使用枚举。示例提供 Java 与 Python 实现。

一、从位掩码到子集

假设有三个物品，按下标编号：

下标	物品	重量
0	茶叶	2
1	面包	3
2	苹果	4

用 3 位二进制数表示是否选择每件物品，第 i 位为 1 表示选择下标 i 的物品：

掩码	二进制	选择的物品	总重量
0	000	空集	0
1	001	茶叶	2
2	010	面包	3
3	011	茶叶、面包	5
4	100	苹果	4
5	101	茶叶、苹果	6
6	110	面包、苹果	7
7	111	茶叶、面包、苹果	9

三个元素共有 2^3 = 8 个子集。一般地，n 个元素每个都有选/不选两种决定，所以子集数为：

2 × 2 × ... × 2 = 2^n

二、把掩码中的位解码成选择

对于掩码 mask，检查第 i 位：

(mask & (1 << i)) != 0

如果表达式为真，就把下标 i 对应的元素放入当前子集。

因此可以分两层遍历：

1. 外层枚举 mask = 0, 1, ..., 2^n - 1。
2. 内层枚举每个元素下标，检查对应位是否为 1。

如果只需要计算每个子集的总重量，伪代码如下：

for mask from 0 to 2^n - 1:
    total_weight = 0
    for i from 0 to n - 1:
        if mask 的第 i 位为 1:
            total_weight += weight[i]
    if total_weight <= capacity:
        记录或处理这个子集

枚举掩码的外层有 2^n 次，每个掩码最多检查 n 个位，所以这版算法的时间复杂度为 O(n × 2^n)。它会逐个重新计算每个子集的重量，适合作为清晰的入门实现。

三、示例问题：哪些物品组合不超重？

物品重量为 [2, 3, 4]，背包容量为 5。找出所有总重量不超过容量的子集。

根据上表，符合条件的是：

• 空集：重量 0；
• {茶叶}：重量 2；
• {面包}：重量 3；
• {苹果}：重量 4；
• {茶叶, 面包}：重量 5。

此处只是在枚举组合并检查容量，没有要求找“最大总重量”的方案，更没有对大量候选做最优化。后续学习背包 DP 时，会看到如何利用子问题结构避免检查所有子集。

四、Java 实现：枚举并筛选子集

import java.util.ArrayList;
import java.util.List;

public class SubsetEnumeration {
    public static List<List<Integer>> subsetsWithinCapacity(
            int[] weights, int capacity) {
        int n = weights.length;
        if (n > 20) {
            throw new IllegalArgumentException(
                "This exhaustive example is limited to 20 items"
            );
        }
        if (capacity < 0) {
            throw new IllegalArgumentException("Capacity must be non-negative");
        }

        int subsetCount = 1 << n;
        List<List<Integer>> result = new ArrayList<>();

        for (int mask = 0; mask < subsetCount; mask++) {
            int totalWeight = 0;
            List<Integer> selected = new ArrayList<>();

            for (int i = 0; i < n; i++) {
                if ((mask & (1 << i)) != 0) {
                    totalWeight += weights[i];
                    selected.add(i);
                }
            }

            if (totalWeight <= capacity) {
                result.add(selected);
            }
        }

        return result;
    }

    public static void main(String[] args) {
        int[] weights = {2, 3, 4};
        List<List<Integer>> result = subsetsWithinCapacity(weights, 5);
        System.out.println(result);
    }
}

输出的下标组合为：

[[], [0], [1], [0, 1], [2]]

物品重量是非负整数，因此增加物品不会让总重量下降；但本例只负责枚举和判断，并没有依赖这个性质进行剪枝。若题目允许负重量或容量含义不同，应重新检查判断条件。

代码将元素数限制为 20，是为了明确这段穷举实现的使用边界，而不是说所有 n <= 20 的题目都一定满足时限。实际能否运行还取决于每个子集的处理成本、语言、机器和题目时限。

五、Python 实现

def subsets_within_capacity(
    weights: list[int], capacity: int
) -> list[list[int]]:
    n = len(weights)
    if n > 20:
        raise ValueError("This exhaustive example is limited to 20 items")
    if capacity < 0:
        raise ValueError("capacity must be non-negative")

    result: list[list[int]] = []
    subset_count = 1 << n

    for mask in range(subset_count):
        total_weight = 0
        selected: list[int] = []

        for i, weight in enumerate(weights):
            if mask & (1 << i):
                total_weight += weight
                selected.append(i)

        if total_weight <= capacity:
            result.append(selected)

    return result

assert subsets_within_capacity([2, 3, 4], 5) == [
    [],
    [0],
    [1],
    [0, 1],
    [2],
]

与 Java 版本一样，这个实现按掩码从小到大遍历，因此结果顺序也一致。若题目不要求顺序，通常只比较结果集合，不应依赖枚举顺序。

六、只遍历掩码中的已选元素

双层循环每次都会检查 n 个位置。若某个掩码中只有少数位为 1，可以反复移除最低位的 1，只访问选中的元素。

对于非零掩码 mask：

lowest_bit = mask & -mask

lowest_bit 只保留最低位的 1。它的位下标可通过 bit_length 求出（Python）或通过循环/标准库位操作求出（Java）。

还有一种更直接的技巧：

mask = mask & (mask - 1)

这会清除最低位的 1。不断清除，就能逐个处理所有选中位，循环次数等于子集大小，而不是元素总数。

这种优化可把每个子集的位扫描成本降到与子集大小成正比，但枚举所有子集时，所有子集大小之和仍为 n × 2^(n-1)。因此若要把每个子集都完整展开，整体复杂度仍是 O(n × 2^n) 量级；优化减少常数和空位检查，不会消除指数级状态数量。

七、复杂度与适用范围

时间复杂度

• 只生成 2^n 个掩码并对每个掩码做常数时间判断：O(2^n)。
• 对每个掩码检查全部 n 个元素：O(n × 2^n)。
• 如果把每个子集都输出，输出本身包含 n × 2^(n-1) 个元素引用，写出这些结果需要相应的总时间和空间。

空间复杂度

只保存当前掩码和总重量时，额外工作空间可以是 O(1)。

示例代码把所有符合条件的子集保存在结果列表中，所以空间还要加上结果本身的大小；最坏情况下所有子集都符合，结果空间可达到 O(n × 2^n)。

什么时候适合？

• 元素数量很小，且题目需要检查所有组合；
• 这是一个简单、可信的暴力基线，用来对比后续优化；
• 每个子集的判断可以快速完成，且 2^n 在时限内可接受。

什么时候不适合？

• n 较大，导致 2^n 已经无法遍历；
• 题目只问最优值，而问题有可利用的动态规划、贪心或剪枝结构；
• 需要保存全部子集，输出量本身就超出内存限制。

元素数每增加 1，子集数量翻倍。复杂度分析时要先用输入范围估算 2^n，不要只看循环代码有几行。

八、常见错误

1. 漏掉掩码 0：它代表空集，很多组合题都要求考虑。
2. 循环终点写成 mask <= 2^n：合法掩码最大是 2^n - 1，上界应为不包含 2^n。
3. 位与优先级不清楚：显式写 (mask & (1 << i)) != 0。
4. 把位下标和元素下标搞反：本文约定第 i 位对应 weights[i]。
5. 整数移位溢出或越界：Java 固定宽度整数必须限制元素数或使用合适的类型；即便改用 long，仍有位数上限。
6. 低估输出空间：保存所有子集可能比只遍历掩码昂贵得多。
7. 把“能枚举”误当成“应该枚举”：枚举适用于小规模；大规模时应寻找可复用子问题、剪枝或更强的结构。

九、从枚举到动态规划

二进制枚举是一个很好的基线：它系统地检查每一种选择，容易证明“没有漏解”。但当多个子集之间存在重叠计算时，继续逐个枚举会浪费时间。

例如背包问题只要求在容量限制下求最大价值时，动态规划可以利用“考虑前 i 件物品、容量为 c”这样的子问题状态，避免重新计算大量相似组合。后续路线会先学习线性和序列 DP，再专门展开背包 DP。

二进制枚举和状态压缩 DP 也有联系：前者把一个集合编码成掩码并逐个遍历；后者把掩码作为 DP 状态，只计算可达或有用的状态。

小结

有 n 个可选元素时，每个子集可用一个 n 位掩码表示。枚举 0 到 2^n - 1，检查每一位，就能遍历全部子集。它简单、完整，适合小规模问题和建立基线；但状态数量是指数级的，必须根据 n 和每个状态的处理成本评估是否可行。

下一篇将讨论打表：当所有查询都落在一个有限且可预计算的范围内时，如何用预处理换取后续查询速度，并与二进制枚举、记忆化搜索作比较。