二进制枚举

在计算一些选择问题时，例如从 n 件物品中选出 m 件，m 属于 [0, n], 求所有的方案，其中 n 不大。

这时可以使用二进制暴力枚举。原理是我们可以使用一个数字 n 的二进制中第 x 位代表第 x 个物品是否被选中。例如，对于 3 个物品，我们可以用 3 位二进制数来表示是否被选中。例如，000 表示都不选，111 表示都选，101 表示选第 1 和第 3 个物品。

当 n 自增时，我们可以通过遍历 0 到 2^n-1 的二进制数来枚举所有的方案。

CPP 中可以使用(n>>i)&1来判断第 i 位是否为 1。

例题

92. 递归实现指数型枚举

从 1∼n 这 n 个整数中随机选取任意多个，输出所有可能的选择方案。

输入格式

输入一个整数 n 。

输出格式 每行输出一种方案。

同一行内的数必须升序排列，相邻两个数用恰好 1 个空格隔开。

对于没有选任何数的方案，输出空行。

数据范围

1≤n≤15

输入样例：

输出样例：

答案：

#include <iostream>

using namespace std;

int main() {
    int n;
    cin >> n;

    int ed = (1 << n); // 2^(n-1) + 1 即 2^n
    for (int i = 0; i < ed; ++i) {
        for (int j = 0; j < n; ++j) {
            if ((i >> j) & 1) {
                cout << j + 1 << " ";
            }
        }
        cout << "\n";
    }

    return 0;
}