Enumerate

枚举在做什么

**枚举(Enumeration / Brute Force)**是最诚实的算法:把所有候选答案试一遍,取最优或计数。

复杂度通常是指数级,所以枚举不是"随便写个 for",而是:如何高效、不重不漏地遍历答案空间。

核心三问:
1. 答案空间有多大?(决定可行性)
2. 怎么遍历才不重不漏?(子集 / 排列 / 组合)
3. 哪些分支可以提前砍掉?(剪枝)

子集枚举

二进制法(最常用)

nn 个元素的每个子集,对应一个nn 位二进制数:第ii 位为 1 表示选了第ii 个。

// 枚举 [0, 2^n) 的每个数
for (int mask = 0; mask < (1 << n); mask++) {
    // mask 表示一个子集
    for (int i = 0; i < n; i++) {
        if (mask & (1 << i)) {
            // 第 i 个元素被选中
        }
    }
}

复杂度:O(n⋅2n)O(n \cdot 2^n)。n≤20n \le 20 时可接受(20×10620 \times 10^6 次)。

遍历子集的子集

// 枚举 mask 的所有子集(常用于子集 DP)
for (int sub = mask; sub; sub = (sub - 1) & mask) {
    // sub 是 mask 的子集
}

这个技巧的总复杂度是O(3n)O(3^n)(而不是4n4^n),是所有子集的子集数量之和:

∑mask2popcount(mask)=3n\sum_{mask} 2^{popcount(mask)} = 3^n

写法要点:sub = (sub - 1) & mask 保证结果始终是 mask 的子集,循环到 sub == 0 结束(空集)。

位运算技巧速查

mask & (1 << i)          // 第 i 位是否为 1
mask | (1 << i)          // 设置第 i 位为 1
mask & ~(1 << i)         // 清除第 i 位
mask ^ (1 << i)          // 翻转第 i 位
mask & (mask - 1)        // 清除最低位的 1
mask & -mask             // 只保留最低位的 1(lowbit)
__builtin_popcount(mask) // 1 的个数
__builtin_ctz(mask)      // 末尾 0 的个数(最低位 1 的位置)

排列枚举

next_permutation

vector<int> a = {1, 2, 3};
sort(a.begin(), a.end());          // 必须从字典序最小的开始
do {
    // 处理这个排列
} while (next_permutation(a.begin(), a.end()));

注意:必须先排序,否则从当前排列开始,只枚举到后面的。

复杂度:O(n⋅n!)O(n \cdot n!)。n≤10n \le 10 可接受(10!=3.6×10610! = 3.6 \times 10^6),n=12n = 12 就4.8×1084.8 \times 10^8 了。

手写 DFS

vector<int> cur;
vector<bool> used(n, false);

void dfs(int dep) {
    if (dep == n) {
        // cur 是一个完整排列
        return;
    }
    for (int i = 0; i < n; i++) {
        if (used[i]) continue;
        used[i] = true;
        cur.push_back(a[i]);
        dfs(dep + 1);
        cur.pop_back();            // 回溯
        used[i] = false;           // 回溯
    }
}

DFS 相比 next_permutation 的优势:可以在递归过程中剪枝(比如前缀已经不合法就直接返回)。

组合枚举

从nn 个里选kk 个,不关心顺序:

void dfs(int start, int dep) {
    if (dep == k) { /* 处理 cur */ return; }
    // 剪枝:剩下的元素不够填满
    if (n - start < k - dep) return;
    for (int i = start; i < n; i++) {
        cur.push_back(a[i]);
        dfs(i + 1, dep + 1);       // 从 i+1 开始,保证不重复且递增
        cur.pop_back();
    }
}

关键:从 start 开始而不是从 0,这样保证选出的索引递增,天然去重({1,2} 和 {2,1} 只会出现一次)。

剪枝

枚举的复杂度是指数的,剪枝是从指数里抠出可行性的唯一手段。

常见剪枝策略

策略做法适用
可行性剪枝当前部分解已经不可能满足条件 → 返回约束满足问题
最优性剪枝当前解的下界已≥\ge 已知最优 → 返回求最值
顺序剪枝按某种顺序枚举,提前找到好解求最值
对称性剪枝排除本质相同的分支(如规定 a[0] <= a[1])有对称结构
记忆化相同状态只算一次有重叠子问题

最优性剪枝示例

int best = INF;
void dfs(int dep, int cost) {
    if (cost >= best) return;          // 最优性剪枝:不可能更优
    if (dep == n) { best = min(best, cost); return; }
    ...
}

更进一步:估算剩余部分的最小可能代价(下界),如果 cost + lower_bound >= best 就剪掉。这个下界越紧,剪枝越有效。

剪枝的效果

无剪枝:   O(2^n)
有剪枝:   实际访问节点数可能降到 O(n^k) 甚至更低

但剪枝不改变最坏复杂度,只能改善实际表现。这就是为什么有些题"随机数据能过,精心构造的数据过不了"。

Meet-in-the-Middle(折半枚举)

当nn 在 40 左右时(2402^{40} 太大,2202^{20} 可以),把问题劈成两半。

原问题: 从 40 个数里选若干个,和等于 target      → 2^40,不可行

折半:
  1. 枚举前 20 个的所有子集和 → 2^20 个数,存起来(排序)
  2. 枚举后 20 个的所有子集和 s → 在第一个集合里二分查找 target - s
  
复杂度: O(2^20 · log(2^20)),可行
// 从 n 个数中选若干个,和恰好为 target
vector<long long> half1, half2;

void gen(const vector<long long>& a, int l, int r, vector<long long>& out) {
    int m = r - l;
    for (int mask = 0; mask < (1 << m); mask++) {
        long long s = 0;
        for (int i = 0; i < m; i++)
            if (mask & (1 << i)) s += a[l + i];
        out.push_back(s);
    }
}

bool solve(const vector<long long>& a, long long target) {
    int n = a.size(), mid = n / 2;
    gen(a, 0, mid, half1);
    gen(a, mid, n, half2);
    sort(half1.begin(), half1.end());
    for (long long s : half2) {
        if (binary_search(half1.begin(), half1.end(), target - s))
            return true;
    }
    return false;
}

识别信号:nn 在 30~45 之间,且问题是"选/不选"的组合型。

枚举的规模化技巧

双指针替代二重循环

// 朴素:O(n^2)
for (int i = 0; i < n; i++)
    for (int j = i + 1; j < n; j++) { /* ... */ }

// 若满足某种单调性,可双指针:O(n)
int j = n - 1;
for (int i = 0; i < n; i++) {
    while (j > i && !check(i, j)) j--;
    // ...
}

条件:随着ii 增大,jj 的最优位置单调不增。这是把O(n2)O(n^2) 降到O(n)O(n) 的关键。

预处理 + 枚举

// 枚举 a[i] + a[j] + a[k] == target 的 O(n^2) 做法:
// 先枚举所有 a[i] + a[j],存进哈希表;再枚举 a[k],查 target - a[k]
unordered_map<long long, int> cnt;
for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++)
        cnt[a[i] + a[j]]++;
long long ans = 0;
for (int k = 0; k < n; k++)
    ans += cnt[target - a[k]];

思想:把三重枚举拆成"枚举两重 + 查表一重"。

子集枚举的典型应用

状态压缩 DP

// TSP: dp[mask][i] = 访问了 mask 中的城市,当前在 i 的最短路径
int dp[1 << N][N];
memset(dp, 0x3f, sizeof dp);
dp[1][0] = 0;
for (int mask = 1; mask < (1 << N); mask++) {
    for (int i = 0; i < N; i++) {
        if (!(mask & (1 << i))) continue;
        for (int j = 0; j < N; j++) {
            if (mask & (1 << j)) continue;
            int nmask = mask | (1 << j);
            dp[nmask][j] = min(dp[nmask][j], dp[mask][i] + dist[i][j]);
        }
    }
}

复杂度O(2n⋅n2)O(2^n \cdot n^2),n≤20n \le 20。

子集 DP / SOS DP

// F[mask] = sum of A[sub] for all sub ⊆ mask
for (int i = 0; i < n; i++)
    for (int mask = 0; mask < (1 << n); mask++)
        if (mask & (1 << i))
            F[mask] += F[mask ^ (1 << i)];

复杂度O(n⋅2n)O(n \cdot 2^n)(比枚举子集的子集的O(3n)O(3^n) 快)。

复杂度参考

手法复杂度可行的nn
全排列O(n!)O(n!)n≤10n \le 10
子集枚举O(2n)O(2^n)n≤25n \le 25
子集 DPO(n⋅2n)O(n \cdot 2^n)n≤22n \le 22
子集的子集O(3n)O(3^n)n≤15n \le 15
Meet-in-the-middleO(2n/2⋅n)O(2^{n/2} \cdot n)n≤45n \le 45
组合枚举(nk)\binom{n}{k}O((nk)⋅k)O(\binom{n}{k} \cdot k)取决于(nk)\binom{n}{k}

n!n! 增长最快:10!=3.6×10610! = 3.6 \times 10^6,12!=4.8×10812! = 4.8 \times 10^8,15!=1.3×101215! = 1.3 \times 10^{12}。超过 12 就必须换思路。

常见坑

  • 1 << n 溢出:n≥31n \ge 31 时 1 << n 是 int 溢出。用 1LL << n
  • next_permutation 前没排序:漏掉字典序更小的排列
  • 回溯忘了恢复现场:used[i] 没置回 false,cur 没 pop
  • 组合枚举从 0 开始导致重复:应从 start 开始
  • 剪枝条件写反:把合法解剪掉了
  • 枚举顺序导致 TLE:先枚举约束强的变量("最少选择优先"),能更快触发剪枝
  • Meet-in-the-middle 的空间:2202^{20} 个 long long 是 8 MB,还可接受;2252^{25} 就 256 MB 了
  • 状态压缩 DP 的空间:dp[1<<20][20] 是106×20×410^6 \times 20 \times 4 字节 = 80 MB,注意内存限制