中 · 位掩码

枚举子集

对 {1, 2, 3} 逐个问：在还是不在？这是个是非题，而一排是非答案就是一个二进制数。n 个元素给出 2^n 个子集 —— 从 1 数到 2^n − 1 就能全部走到。

一句话答案对从 1 到 2^n − 1 的每个 mask，打印所有置位的那个 i（用 <code>mask % 2</code> 测试，然后 <code>mask /= 2</code>）—— 不需要递归。

题目

输入: 一个整数 n（1 ≤ n ≤ 8）。

输出: {1, …, n} 的所有非空子集，每行一个，行内数字从小到大，子集按二进制掩码顺序排列（n = 3 时为：1、2、1 2、3、1 3、2 3、1 2 3）。

样例:

输入输出
21
2
1 2
31
2
1 2
3
1 3
2 3
1 2 3

空子集是掩码 0，而判题不想要一个空白首行 —— 从 1 开始数。只要从 i = 1 往上测位，子集内的数字自然就是升序。

你的解答

main.cpp — 你的解答
「运行我的输入」用的自定义输入

判题在浏览器本地运行。死循环会在 3 秒后被自动中断 —— 但还是确保每个循环都有出口。代码随打随存。

卡住了？提示

提示 1 — 第 i 位表示「i 在集合里」

约定掩码的第 i−1 位（从 0 数）决定要不要打印数字 i。n = 3 时掩码 0b101 对应子集 {1, 3}。约定一旦定死，打印子集就是走一遍它的各个位。

提示 2 — 用 % 和 / 解码各个位

不需要移位运算符：把掩码抄进临时变量再剥 —— if (m % 2 == 1) 打印 i; 然后 m /= 2;，i 从 1 走到 n。这正是 二进制表示 里那个拆位循环，只是指向了二进制位而不是十进制位。

提示 3 — 用乘法构造 2^n

把 limit 从 1 开始翻倍 n 次（循环里 limit *= 2），掩码就是 1 … limit - 1。n = 8 时是 255 个子集 —— 2^n 涨得飞快，这题还能打印是因为判题把 n 限得很小。

题解（先自己试试！） 
#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    int limit = 1;
    for (int i = 0; i < n; i++) limit *= 2;

    for (int mask = 1; mask < limit; mask++) {
        int m = mask;
        bool first = true;
        for (int i = 1; i <= n; i++) {
            if (m % 2 == 1) {
                if (!first) cout << " ";
                cout << i;
                first = false;
            }
            m /= 2;
        }
        cout << endl;
    }
    return 0;
}

「子集即掩码」是暴力法的脊梁：n ≤ 20 时，试遍 2^n 个子集是合法策略，以后它还是状态压缩 DP 的地基。注意你没用递归 —— 二进制表示 里的计数循环和这个循环是同一台机器，只是指向了不同的尺度。

深度解析

为什么这样做对

{1..n} 的子集 = 对每个元素做一次「在/不在」的判断,而一排固定的是非答案就是一个二进制数。所以从 1 数到 2^n − 1,恰好把每个非空子集各枚举一次;测第 i−1 位(m % 2,然后 m /= 2)就知道 i 在不在。

代价

时间 O(2^n × n) —— 每个 mask 花 O(n) 解码 —— 除循环变量外 O(1) 空间。n = 10 是一万行;n = 20 已经两千万行:位掩码暴力有硬上限。

常见错法

  • mask 循环从 0 开始,会先打印一个空行(空子集),判题直接判错 —— 从 1 开始。
  • 忘了临时变量:在测 m % 2 的同一句里做 m /= 2,位还没读到就被吃掉了。先抄一份,再剥。
  • 把空格打在最后一个值后面而不是值与值之间 —— 判题会掐行尾空格,但首数字前的空格是错答,不是风格问题。

下一步

同一个「% / 剥位」循环,指向十进制数就是 二进制表示;指向「数有几个 1」就是 数一数 1 的个数。一个循环,三道题。

记住这两句

  • {1..n} 的子集就是 n 位二进制数;第 i 位 = 「i 在不在」。
  • 2^n 是暴力预算:n = 10 没问题,n = 20 一百万,n = 40 不可能。
🐞 这段是错的 —— 点开,亲手让它挂一次

先除后测 —— m /= 2 和 m % 2 挤在同一句里,位还没读就被吃掉了

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    int limit = 1;
    for (int i = 0; i < n; i++) limit *= 2;
    for (int mask = 1; mask < limit; mask++) {
        int m = mask;
        for (int i = 1; i <= n; i++) {
            m /= 2;                  // bug: eats bit 0 before testing
            if (m % 2 == 1) cout << i << " ";
        }
        cout << endl;
        // also: trailing space instead of separators
    }
    return 0;
}