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、3 | 13 不在;10 在 | 找到 3+10=13 |
窄屏可左右滑动表格,阅读完整计算与理由。
左右半的匹配覆盖完整选择,找到任一组合就可返回 True。
04为什么这个方法成立
- 子集和扩展包含选与不选两种分支,归纳覆盖一半中的所有子集。
- 任何完整子集都可拆成两半,目标成立必有对应补数。
- 补数命中反过来也给出合法的两个不相交子集。
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从手算到独立迁移
先写出自己的结果和理由,再展开提示或解析。三题依次检查具体执行、边界条件和方法迁移。
target=0 是否总可行?
需要一点提示
允许选择零个元素吗?
查看解析与答案
若允许空子集则总可行,两个半列表都含 0。
有负数还能用吗?
需要一点提示
是否使用过和的单调性?
查看解析与答案
可以,完整枚举与补数判断不依赖正负。
如何找最接近 target 而非恰好等于?
需要一点提示
哈希不能寻找最近邻。
查看解析与答案
把一半排序,对另一半的补数做二分,比较插入点两侧,保留最小差。