专题进阶 · 搜索与回溯推荐总顺序 · 第 36 / 148 课

把子集和拆成两半,推导指数降低与内存增加的交换关系。

先学会这些,再进入本课 回溯 集合
还有 2 节先修课未标记掌握;已具备基础时可以直接学习,遇到障碍再沿链接补课。
专题详解 · 搜索与回溯

折半搜索Meet in the Middle

把指数搜索拆成两半,分别枚举再匹配,常把 2ⁿ 降至约 2⁽ⁿ⁄²⁾ 的规模。

建议 40 分钟 · 含手算、代码与三层练习

本课要建立的能力

把子集和拆成两半,推导指数降低与内存增加的交换关系。

先手算,再对照代码;理解为什么成立,最后用改变条件的练习检查迁移能力。

01先把问题说具体

40 个整数中能否选择若干个使总和等于目标?完整枚举有约一万亿个子集,动态规划又受巨大值域限制。

02一步步得到方法

枚举两半,而不是枚举一半答案

每个完整子集都唯一拆成左半子集与右半子集。分别生成两边所有可能和 L、R,只要存在 l+r=target 即可。将 R 放入集合,逐个检查 target−l 是否存在。

拆开之后不是只考虑一半元素,而是把两个指数规模列表通过匹配连接。两边各约 2^(n/2) 项,明显小于 2^n,但内存也要能容纳这些和。

逐元素扩展子集和

从 [0] 开始表示空子集。加入 x 时,旧列表中每个和 s 都产生一个新和 s+x,同时保留不选 x 的旧和。新和必须由旧快照生成,不能一边遍历一边无界追加。

允许负数时仍然正确,因为方法依赖完整枚举而非正数单调性。若要恢复具体子集,可同时保存位掩码;若只问存在性,重复和可以去重。

把枚举规模与匹配成本分开

拆成两半后,各有约 2^(n/2) 个子集结果。收益来自只生成两张表,再通过哈希、排序或双指针寻找匹配;若仍把左右结果两两比较,就重新回到约 2^n 对组合。

元素取值有重复时,不同子集可能得到同一和。只问存在性可以去重;统计方案数时必须保留频次。先明确输出要求,才知道应该用集合还是计数字典。

03把一个小例子完全算清楚

[3,5,8,10],target=13,拆成 [3,5] 与 [8,10]。

步骤计算与状态为什么这样做
左半[0,3,5,8]四个子集和
右半{0,8,10,18}建立成员索引
试 l=0、313 不在;10 在找到 3+10=13

窄屏可左右滑动表格,阅读完整计算与理由。

左右半的匹配覆盖完整选择,找到任一组合就可返回 True。

04为什么这个方法成立

  1. 子集和扩展包含选与不选两种分支,归纳覆盖一半中的所有子集。
  2. 任何完整子集都可拆成两半,目标成立必有对应补数。
  3. 补数命中反过来也给出合法的两个不相交子集。

05把推导翻译成代码

Python · 可独立运行的教学实现

def subset_sums(a):
    sums = [0]
    for x in a:
        sums += [s + x for s in sums]
    return sums

def subset_sum(a, target):
    mid = len(a) // 2
    right = set(subset_sums(a[mid:]))
    return any(target - s in right for s in subset_sums(a[:mid]))

逐个理解关键决定

[s + x for s in sums]
先完整生成新列表,再追加,避免重复使用当前元素。
target - s in right
将二重笛卡尔积匹配变成哈希查询;直接双重循环会恢复到 O(2^n)。

06时间、空间与实现范围

哈希平均模型下时间和空间均约 O(2^(n/2)),整数加法与哈希位数成本另计。

n=40 时每半约 2^20 项;n=80 时每半约 2^40,仍不可承受,指数只是降低没有消失。

07改变条件,检查哪里会出错

两半列表直接两两配对

会做 2^(n/2)·2^(n/2)=2^n 次比较;用集合或排序后二分。

把负数和正数混用时沿用剪枝

子集和含负数时,超过目标不代表无解;折半枚举本身可处理负数,额外剪枝需要证明。

08从手算到独立迁移

先写出自己的结果和理由,再展开提示或解析。三题依次检查具体执行、边界条件和方法迁移。

练习 1 · 复现与理解

target=0 是否总可行?

需要一点提示

允许选择零个元素吗?

查看解析与答案

若允许空子集则总可行,两个半列表都含 0。

练习 2 · 边界与辨析

有负数还能用吗?

需要一点提示

是否使用过和的单调性?

查看解析与答案

可以,完整枚举与补数判断不依赖正负。

练习 3 · 变式与迁移

如何找最接近 target 而非恰好等于?

需要一点提示

哈希不能寻找最近邻。

查看解析与答案

把一半排序,对另一半的补数做二分,比较插入点两侧,保留最小差。

继续深入这个专题

本站例子、推导与教学代码独立编写。以下是相关教材、作者论文或官方文档,可继续核对定义、证明与更完整的工程实现。

MIT 6.006 · 算法讲义

理解之后,继续递进

继续当前专题:二分答案 →。跨专题先修要求会在下一课顶部提示。

能解释手算中的每一步,并独立完成迁移题后,再标记掌握。