二进制枚举法：高效解决子集问题的核心技巧

1. 二进制枚举法入门：为什么它是子集枚举的首选

第一次接触子集枚举问题时，我尝试用递归实现，结果写了20多行代码还容易出错。直到发现二进制枚举法，3行核心代码就能搞定，简直相见恨晚。这种方法特别适合处理n≤20的小规模数据，比如LeetCode上的子集问题、组合问题，或者状态压缩DP的预处理。

二进制枚举的核心思想非常巧妙：用一个整数的二进制位来表示元素的选择状态。比如数字5的二进制是101，对应到数组[1,2,3]就表示选择第1和第3个元素（注意从0开始计数），即子集[1,3]。这种表示方法不仅节省空间，而且操作效率极高。

关键提示：二进制枚举法的时间复杂度是O(n·2ⁿ)，这意味着当n=20时，循环次数将达到约100万次。虽然看起来很大，但在现代CPU上完全可以在1秒内完成。

2. 核心原理深度解析

2.1 二进制与子集的映射关系

让我们用数组[1,2,3,4]为例，彻底理解这种映射关系。4个元素意味着有2⁴=16种可能的子集。每个子集对应一个4位二进制数：

这种映射的妙处在于，二进制的每一位天然代表了"选"或"不选"两种状态。第j位为1表示选择数组中第j个元素，为0则不选。

2.2 位运算的关键作用

实现这种映射需要三个关键位运算：

1. 左移运算(<<)：1 << n计算出2ⁿ，即所有可能的子集数量
2. 按位与(&)：i & (1 << j)检查数字i的第j位是否为1
3. 右移运算(>>)：也可以使用(i >> j) & 1来检查第j位

理解这些位运算的行为对掌握二进制枚举至关重要。举个例子，当i=5(0101)，j=2时：

• 1 << j得到4(0100)
• 5 & 4等于4(0100)，非零表示第2位为1
• 而(5 >> 2) & 1得到1，同样表明第2位为1

3. 完整实现与逐行解析

3.1 基础实现代码

下面是带详细注释的完整实现，我们以数组[1,2,3,4]为例：

cpp复制#include <iostream>
using namespace std;

int main() {
    int a[] = {1, 2, 3, 4};  // 原始数组
    int n = sizeof(a)/sizeof(a[0]);  // 自动计算数组长度