14 · 枚举与暴力：把搜索空间数清楚

最省事的写法是三层的循环 a, b, c 各 100..999，再拆位检查——7.3×10⁸ 个三元组，每个还要拆 9 位，总计 6×10⁹ 次操作，1 秒的题必死。

关键观察：题目给了比例。只要 a 定了，b = 2a、c = 3a 就定了。枚举对象从“三个数”换成“一个数”，方案数从 10⁹ 掉到 10²。这就是“数清楚”的第一层收益：不用算法，只换视角。

a 的范围也不是 100..999：a 自己得是三位数、不含 0、数字互不相同，最小就是 123；c = 3a 也得是三位数（3a ≤ 987），所以 a ≤ 329。能算出边界就不要硬写 999。

剩下的活是判重：三个三位数一共 9 个数字，要求恰好是 1..9 各一次。用 cnt[10] 数每个数字出现的次数，出现 0 或某个数字第二次出现就否决，最后检查 1..9 是否都恰好一次。

#include <bits/stdc++.h>
using namespace std;

int main() {
    for (int a = 123; a <= 329; ++a) {          // 3a ≤ 987 ⇒ a ≤ 329
        int cnt[10] = {0};                      // cnt[d]：数字 d 出现了几次
        int p[3] = {a, 2 * a, 3 * a};           // 由比例生成，不用三层循环
        bool ok = true;

        for (int t = 0; t < 3 && ok; ++t) {
            int x = p[t];                       // 拆 x 的三位，x 是副本，不动 p[t]
            for (int j = 0; j < 3; ++j) {
                int d = x % 10;
                x /= 10;
                if (d == 0 || ++cnt[d] > 1) {   // 出现 0 或重复，立刻否决
                    ok = false;
                    break;
                }
            }
        }
        if (!ok) continue;

        bool all = true;                        // 1~9 是否每个恰好出现一次
        for (int d = 1; d <= 9; ++d)
            if (cnt[d] != 1) { all = false; break; }
        if (all) cout << a << " " << 2 * a << " " << 3 * a << "\n";
    }
    return 0;
}

n 个元素“选或不选”，一共 2ⁿ 种结果。把每种结果编码成一个整数：第 i 位是 1 表示选第 i 个元素。于是 for (int mask = 0; mask < (1 << n); ++mask) 这一层循环就把所有子集走完了。

它比 n 层嵌套循环短得多，也比递归早 7 节就能用（第 21 节才讲递归）。代价是不能剪枝：2ⁿ 个方案一个不落。

// 演示：n ≤ 20，统计元素和恰好等于 S 的子集个数（不含空集）
int n = 5, S = 10;
int a[5] = {1, 2, 3, 4, 5};
int ans = 0;

for (int mask = 0; mask < (1 << n); ++mask) {   // 2⁵ = 32 个 mask，一个 mask 一个子集
    int sum = 0;
    for (int i = 0; i < n; ++i)
        if ((mask >> i) & 1) sum += a[i];       // 第 i 位是 1 ⇒ 选 a[i]
    if (mask != 0 && sum == S) ++ans;           // 空集的和是 0，本题不要
}
cout << ans << "\n";                            // 3

把这张表记住比记住代码有用：看到 n ≤ 20 就想二进制枚举，看到 n ≥ 25 就换方法。如果题目还要求“恰好选 k 个”，用 __builtin_popcount(mask) == k 筛掉大部分方案——C(n, k) / 2ⁿ 的比例可以从 C(20, 10) / 2²⁰ ≈ 18% 手算出来。

n = 40 时 2⁴⁰ ≈ 1.1×10¹²，一秒跑不完。但把数组切成两半，每半 20 个，各枚举 2²⁰ ≈ 1.05×10⁶ 个子集和；再让“左半取 s、右半取 S − s”配对就行。

配对靠排序 + 二分，正好用上第 13 节的 lower_bound 与 upper_bound。这就是折半搜索（meet in the middle）：把一次 2ⁿ 的枚举，换成两次 2^(n/2) 的枚举加一次二分。

int h = n / 2;                                 // 切成 20 + 20
vector<long long> L, R;

for (int mask = 0; mask < (1 << h); ++mask) {  // 左半：2²⁰ 个子集和
    long long s = 0;
    for (int i = 0; i < h; ++i)
        if ((mask >> i) & 1) s += a[i];
    L.push_back(s);
}
for (int mask = 0; mask < (1 << (n - h)); ++mask) {   // 右半：2²⁰ 个子集和
    long long s = 0;
    for (int i = 0; i < n - h; ++i)
        if ((mask >> i) & 1) s += a[h + i];           // 原数组下标是 h + i
    R.push_back(s);
}

sort(R.begin(), R.end());                      // 只排一半

long long ans = 0;
for (long long s : L)                          // 左半每个和，去右半里数 S−s 出现几次
    ans += upper_bound(R.begin(), R.end(), S - s)
         - lower_bound(R.begin(), R.end(), S - s);

代价是内存：两个数组各存约 10⁶ 个 long long，各 8 MB，还扛得住。再大就得换个思路。记住这个手势：指数太大就砍一半——枚举一半、排序一半、另一半去查。