Enumerate
枚举在做什么
**枚举(Enumeration / Brute Force)**是最诚实的算法:把所有候选答案试一遍,取最优或计数。
复杂度通常是指数级,所以枚举不是"随便写个 for",而是:如何高效、不重不漏地遍历答案空间。
核心三问:
1. 答案空间有多大?(决定可行性)
2. 怎么遍历才不重不漏?(子集 / 排列 / 组合)
3. 哪些分支可以提前砍掉?(剪枝)子集枚举
二进制法(最常用)
个元素的每个子集,对应一个 位二进制数:第 位为 1 表示选了第 个。
// 枚举 [0, 2^n) 的每个数
for (int mask = 0; mask < (1 << n); mask++) {
// mask 表示一个子集
for (int i = 0; i < n; i++) {
if (mask & (1 << i)) {
// 第 i 个元素被选中
}
}
}复杂度:。 时可接受( 次)。
遍历子集的子集
// 枚举 mask 的所有子集(常用于子集 DP)
for (int sub = mask; sub; sub = (sub - 1) & mask) {
// sub 是 mask 的子集
}这个技巧的总复杂度是(而不是),是所有子集的子集数量之和:
写法要点: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()));注意:必须先排序,否则从当前排列开始,只枚举到后面的。
复杂度:。 可接受(), 就 了。
手写 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 的优势:可以在递归过程中剪枝(比如前缀已经不合法就直接返回)。
组合枚举
从 个里选 个,不关心顺序:
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} 只会出现一次)。
剪枝
枚举的复杂度是指数的,剪枝是从指数里抠出可行性的唯一手段。
常见剪枝策略
| 策略 | 做法 | 适用 |
|---|---|---|
| 可行性剪枝 | 当前部分解已经不可能满足条件 → 返回 | 约束满足问题 |
| 最优性剪枝 | 当前解的下界已 已知最优 → 返回 | 求最值 |
| 顺序剪枝 | 按某种顺序枚举,提前找到好解 | 求最值 |
| 对称性剪枝 | 排除本质相同的分支(如规定 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(折半枚举)
当 在 40 左右时( 太大, 可以),把问题劈成两半。
原问题: 从 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;
}识别信号: 在 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--;
// ...
}条件:随着 增大, 的最优位置单调不增。这是把 降到 的关键。
预处理 + 枚举
// 枚举 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]);
}
}
}复杂度,。
子集 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)];复杂度(比枚举子集的子集的 快)。
复杂度参考
| 手法 | 复杂度 | 可行的 |
|---|---|---|
| 全排列 | ||
| 子集枚举 | ||
| 子集 DP | ||
| 子集的子集 | ||
| Meet-in-the-middle | ||
| 组合枚举 | 取决于 |
增长最快:,,。超过 12 就必须换思路。
常见坑
1 << n溢出: 时1 << n是int溢出。用1LL << nnext_permutation前没排序:漏掉字典序更小的排列- 回溯忘了恢复现场:
used[i]没置回 false,cur没 pop - 组合枚举从 0 开始导致重复:应从
start开始 - 剪枝条件写反:把合法解剪掉了
- 枚举顺序导致 TLE:先枚举约束强的变量("最少选择优先"),能更快触发剪枝
- Meet-in-the-middle 的空间: 个
long long是 8 MB,还可接受; 就 256 MB 了 - 状态压缩 DP 的空间:
dp[1<<20][20]是 字节 = 80 MB,注意内存限制
许可协议:CC BY
作者:Davids
本文链接:https://hustjjd.github.io/122d1b7f.html
更新于:2026年11月16日