📖 第 6.4 章：折半搜索（Meet in the Middle）
⏱ 预计阅读时间：40 分钟 | 难度：🟡 中等（USACO Gold 必备）
前置条件
- DFS 回溯（第 5.2.12 章）
- 排序与二分查找（第 3.3 章）
- 位运算（第 2.6 章）
🎯 学习目标
学完本章后，你将能够：
- 理解折半搜索的核心思想：将 O(2^N) 降为 O(2^(N/2) × log)
- 解决「子集和」「N 个数中选 k 个」类的大规模枚举问题
- 将线性搜索空间拆成两半分别处理，再合并答案
6.4.1 问题引入：子集和
原始问题
给定 N 个整数（N ≤ 40），找是否存在一个非空子集，其和恰好等于目标值 target。
朴素暴力： 枚举所有 2^N 个子集，时间 O(2^40) ≈ 10^12，完全不可行。
关键观察： 40 个元素太多，但 20 个元素的 2^20 = 1,048,576 完全可行！
6.4.2 折半搜索的核心思想
将 N 个元素分成两半（各 N/2 个），分别枚举，然后合并。
原数组：[a1, a2, ..., a40]
↓ 分成两半
左半边：[a1, ..., a20] → 枚举所有子集和 → 2^20 个值
右半边：[a21, ..., a40] → 枚举所有子集和 → 2^20 个值
查找：对于左半边的每个子集和 s，
在右半边查找是否有子集和等于 (target - s)
用排序 + 二分查找：O(2^(N/2) × log(2^(N/2))) = O(2^(N/2) × N/2)
时间复杂度： O(2^(N/2) × N)，N=40 时约 20 × 10^6，完全可行！
6.4.3 完整实现：子集和判断
#include <bits/stdc++.h>
using namespace std;
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL);
int n; long long target;
cin >> n >> target;
vector<long long> a(n);
for (long long& x : a) cin >> x;
int half = n / 2;
int left_n = half, right_n = n - half;
// 枚举左半边所有子集和
vector<long long> left_sums;
for (int mask = 0; mask < (1 << left_n); mask++) {
long long s = 0;
for (int i = 0; i < left_n; i++)
if ((mask >> i) & 1) s += a[i];
left_sums.push_back(s);
}
sort(left_sums.begin(), left_sums.end()); // 排序以便二分
// 枚举右半边所有子集和，查找配对
bool found = false;
for (int mask = 0; mask < (1 << right_n); mask++) {
long long s = 0;
for (int i = 0; i < right_n; i++)
if ((mask >> i) & 1) s += a[left_n + i];
// 在左半边查找 target - s
long long need = target - s;
if (binary_search(left_sums.begin(), left_sums.end(), need)) {
found = true;
break;
}
}
cout << (found ? "YES" : "NO") << "\n";
return 0;
}
// 时间：O(2^(N/2) × N)，N=40 时约 4×10^7
// 空间：O(2^(N/2)) 存储左半边子集和
追踪示例（a = [1, 5, 3, 8], target = 9）：
左半边：[1, 5]
子集和：0（空）, 1, 5, 6
排序：[0, 1, 5, 6]
右半边：[3, 8]
mask=01（只含3）：s=3，need=9-3=6，在左半边找 6 → 找到！
输出：YES（子集 {5,3+1=不对...实际是 {1,5} 和 {3}）
验证：1+5+3 = 9 ✓（左={1,5}，右={3}）
6.4.4 计数变体：恰好等于目标的子集数
// 统计和恰好为 target 的子集数量
long long count_subsets(vector<long long>& a, long long target) {
int n = a.size(), half = n / 2;
int left_n = half, right_n = n - half;
// 枚举左半边
vector<long long> left_sums;
for (int mask = 0; mask < (1 << left_n); mask++) {
long long s = 0;
for (int i = 0; i < left_n; i++)
if ((mask >> i) & 1) s += a[i];
left_sums.push_back(s);
}
sort(left_sums.begin(), left_sums.end());
// 枚举右半边，用 lower_bound/upper_bound 统计配对数量
long long ans = 0;
for (int mask = 0; mask < (1 << right_n); mask++) {
long long s = 0;
for (int i = 0; i < right_n; i++)
if ((mask >> i) & 1) s += a[left_n + i];
long long need = target - s;
auto lo = lower_bound(left_sums.begin(), left_sums.end(), need);
auto hi = upper_bound(left_sums.begin(), left_sums.end(), need);
ans += hi - lo; // 等于 need 的个数
}
// 减去空集（若 target == 0，空集被算了一次）
if (target == 0) ans--;
return ans;
}
6.4.5 最大子集和变体
问题： 找和不超过 target 的子集中，和最大的那个。
long long max_subset_sum_le_target(vector<long long>& a, long long target) {
int n = a.size(), half = n / 2;
int left_n = half, right_n = n - half;
// 左半边所有子集和
vector<long long> left_sums;
for (int mask = 0; mask < (1 << left_n); mask++) {
long long s = 0;
for (int i = 0; i < left_n; i++)
if ((mask >> i) & 1) s += a[i];
left_sums.push_back(s);
}
sort(left_sums.begin(), left_sums.end());
// 去重（同一和值只需保留一个，降低后续查找复杂度）
left_sums.erase(unique(left_sums.begin(), left_sums.end()), left_sums.end());
long long ans = 0;
for (int mask = 0; mask < (1 << right_n); mask++) {
long long s = 0;
for (int i = 0; i < right_n; i++)
if ((mask >> i) & 1) s += a[left_n + i];
if (s > target) continue; // 右半边超限，不用找左半边
// 在左半边找最大的 ≤ (target - s) 的值
long long need = target - s;
auto it = upper_bound(left_sums.begin(), left_sums.end(), need);
if (it != left_sums.begin()) {
--it;
ans = max(ans, s + *it);
}
}
return ans;
}
6.4.6 折半搜索 vs 其他方法
| 方法 | 时间复杂度 | 适用场景 |
|---|---|---|
| 暴力枚举 | O(2^N) | N ≤ 20 |
| 折半搜索 | O(2^(N/2) × N) | N ≤ 40 |
| 动态规划（背包） | O(N × target) | target 不大时 |
| 二维 DP | O(N^2) | 特殊结构 |
折半搜索的适用条件：
- 问题可以拆成两个独立的「半问题」
- 两个半问题的结果可以快速合并（通常用排序+二分）
- 总量 N ≤ 40（每半不超过 20）
⚠️ 常见错误
| 错误 | 原因 | 修复方案 |
|---|---|---|
| 左半边子集和溢出 | N=40 且元素值大时，子集和超 int | 用 long long |
| 空集未处理 | mask=0 对应空集，和=0，target=0 时多计 | 若 target=0 且要求非空子集，减 1 |
| 分割不均 | 一半 20 一半 20 vs 1 和 39 效率差很多 | 尽量均分：half = n/2 |
| 二分边界错误 | lower_bound vs upper_bound 混用 | lower_bound 找第一个 ≥，upper_bound 找第一个 > |
💪 练习题
🟢 题目 1：子集和存在性
给定 N（≤40）个整数和 target，判断是否存在非空子集和恰好等于 target。
✅ 完整解答
直接使用 6.4.3 节的代码。
🟡 题目 2：子集和计数
给定 N（≤40）个整数和 target，统计和恰好为 target 的非空子集数量（答案可能很大，对 10^9+7 取模）。
✅ 完整解答
使用 6.4.4 节的计数代码，注意模运算（统计时就取模）。
#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1e9 + 7;
int main() {
int n; long long target;
cin >> n >> target;
vector<long long> a(n);
for (long long& x : a) cin >> x;
int half = n / 2, left_n = half, right_n = n - half;
map<long long, long long> left_cnt; // 用 map 存和→出现次数（便于取模）
for (int mask = 0; mask < (1 << left_n); mask++) {
long long s = 0;
for (int i = 0; i < left_n; i++)
if ((mask >> i) & 1) s += a[i];
left_cnt[s]++;
}
long long ans = 0;
for (int mask = 0; mask < (1 << right_n); mask++) {
long long s = 0;
for (int i = 0; i < right_n; i++)
if ((mask >> i) & 1) s += a[left_n + i];
long long need = target - s;
if (left_cnt.count(need))
ans = (ans + left_cnt[need]) % MOD;
}
if (target == 0) ans = (ans - 1 + MOD) % MOD; // 去掉全空集
cout << ans << "\n";
}
🔴 题目 3：最接近目标的子集和
给定 N（≤40）个正整数和 target，找非空子集中和最大但不超过 target 的那个，输出这个最大和。
✅ 完整解答
直接使用 6.4.5 节的 max_subset_sum_le_target 函数。
追踪（a=[3,5,7,2], target=10）：
左半边 [3,5]：子集和 = [0,3,5,8]，排序后 [0,3,5,8]
右半边 [7,2]：
mask=00 (空)：s=0，need=10，在左找≤10的最大=8 → 答案候选 0+8=8
mask=01 (7)：s=7，need=3，在左找≤3的最大=3 → 答案候选 7+3=10 ✓
mask=10 (2)：s=2，need=8，在左找≤8的最大=8 → 答案候选 2+8=10 ✓
mask=11 (9)：s=9，need=1，在左找≤1的最大=0 → 答案候选 9+0=9
最大答案：10
💡 章节联系： 折半搜索是 USACO Gold 的独特技巧，每年约出现 1 道。它本质上是「暴力搜索 + 聪明合并」，将指数复杂度减半。与状压 DP（第 6.3 章）都处理 2^N 的搜索空间，但折半搜索不需要 DP 递推关系。