📖 第 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 完整实现：子集和判断
💡 CPP 代码（44 行）
#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 计数变体：恰好等于目标的子集数
💡 CPP 代码（33 行）
// 统计和恰好为 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 的子集中，和最大的那个。
💡 CPP 代码（34 行）
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
🔴 题目 4：USACO Gold 风格 — 最优配对
给定 N（N ≤ 40，偶数）个整数，将它们两两配对（共 N/2 对），每对的代价为两数之积，求所有配对代价之和的最小值。
输入： 第一行 N，第二行 N 个整数 a_i（|a_i| ≤ 10^9）。
样例输入：
4
1 -2 3 -4
样例输出： -10（配对 (1,-4) + (-2,3) = -4 + (-6) = -10）
✅ Full Solution
核心思路： N ≤ 40 太大无法暴力枚举所有配对方案。但将 N 个数分成两半（各 N/2 ≤ 20），分别枚举每半内部的配对方案及剩余未配对元素，再用折半搜索合并。
具体地：左半边 N/2 个数中，枚举哪些元素在左半内部配对（用位掩码表示），剩余未配对的元素需要与右半边的未配对元素配对。由于两半的未配对数量必须相同，可以用排序 + DP 合并。
更简洁的做法：因为 N ≤ 40 是偶数，直接枚举所有配对方式用 O((N-1)!!) 仍然太大。改用状压 DP：dp[mask] = 集合 mask 中元素两两配对的最小代价。但 2^40 太大。
折半搜索做法： 将 N 个数分成 A（前 N/2 个）和 B（后 N/2 个）。用状压 DP 分别对 A 和 B 求内部配对的最小代价，再枚举跨组配对。对于跨组配对，枚举 A 中有 k 个元素要与 B 中 k 个元素配对，枚举 A 中选哪 k 个、B 中选哪 k 个，用最小权匹配求最优配对。当 k ≤ 20/2 = 10 时，枚举量可控。
这里给出一个更实际的 O(2^N × N) 状压 DP 解法（N ≤ 20 可行），对 N ≤ 40 需要折半。
折半实现： 把 N 个元素分成两半，对每半用状压 DP 求内部配对最优值。然后枚举两半中哪些元素不参与内部配对（跨组配对），对跨组元素用最优匹配。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1e18;
// 对 half 个元素做状压 DP：dp[mask] = mask 中元素两两配对的最小代价
// mask 必须有偶数个 1
vector<ll> calc_dp(vector<ll>& a) {
int n = a.size();
vector<ll> dp(1 << n, INF);
dp[0] = 0;
for (int mask = 0; mask < (1 << n); mask++) {
if (dp[mask] == INF) continue;
// 找第一个未配对的元素
int i = -1;
for (int j = 0; j < n; j++)
if (!((mask >> j) & 1)) { i = j; break; }
if (i == -1) continue; // 全部已配对
// 枚举与 i 配对的元素 j
for (int j = i + 1; j < n; j++) {
if ((mask >> j) & 1) continue;
int nmask = mask | (1 << i) | (1 << j);
dp[nmask] = min(dp[nmask], dp[mask] + a[i] * a[j]);
}
}
return dp;
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL);
int n; cin >> n;
vector<ll> a(n);
for (ll& x : a) cin >> x;
int half = n / 2;
vector<ll> A(a.begin(), a.begin() + half);
vector<ll> B(a.begin() + half, a.end());
int an = A.size(), bn = B.size();
auto dpA = calc_dp(A);
auto dpB = calc_dp(B);
// 枚举 A 中哪些元素不参与内部配对（要跨组配对）
// 跨组元素数必须为偶数，且不超过 bn
ll ans = INF;
for (int maskA = 0; maskA < (1 << an); maskA++) {
if (dpA[maskA] >= INF) continue;
int crossA = an - __builtin_popcount(maskA); // A 中未配对数
if (crossA > bn) continue;
if (crossA % 2 != 0) continue;
// B 中也必须有 crossA 个未配对
// 枚举 B 中哪些元素不参与内部配对
for (int maskB = 0; maskB < (1 << bn); maskB++) {
if (dpB[maskB] >= INF) continue;
int crossB = bn - __builtin_popcount(maskB);
if (crossB != crossA) continue;
// 收集 A 和 B 中未配对的元素，做最优配对
vector<ll> unA, unB;
for (int i = 0; i < an; i++)
if (!((maskA >> i) & 1)) unA.push_back(A[i]);
for (int i = 0; i < bn; i++)
if (!((maskB >> i) & 1)) unB.push_back(B[i]);
// 对未配对元素做最小权匹配（元素少，可以状压 DP）
int k = crossA;
vector<ll> match_dp(1 << k, INF);
match_dp[0] = 0;
for (int m = 0; m < (1 << k); m++) {
if (match_dp[m] >= INF) continue;
int idx = __builtin_popcount(m); // 当前配对第 idx 个 A 元素
if (idx >= k) continue;
for (int j = 0; j < k; j++) {
if ((m >> j) & 1) continue;
int nm = m | (1 << j);
match_dp[nm] = min(match_dp[nm], match_dp[m] + unA[idx] * unB[j]);
}
}
ans = min(ans, dpA[maskA] + dpB[maskB] + match_dp[(1 << k) - 1]);
}
}
cout << ans << "\n";
}
复杂度分析： 每半状压 DP 时间 O(2^(N/2) × N)，合并时枚举两边掩码 O(2^(N/2) × 2^(N/2)) = O(2^N)，内部匹配 O(2^k × k)。当 N=20 时（每半 10），2^10=1024，合并 1024×1024 ≈ 10^6 可行。对于 N=40 需要更精细的优化（如只枚举 popcount 合法的掩码对）。
💡 章节联系： 折半搜索是 USACO Gold 的独特技巧，每年约出现 1 道。它本质上是「暴力搜索 + 聪明合并」，将指数复杂度减半。与状压 DP（第 6.3 章）都处理 2^N 的搜索空间，但折半搜索不需要 DP 递推关系。