subset-sum · 划分 / 对账

多重子集和 · 把两组数配对

一个真实的对账问题：有两组数，数组 1 与数组 2，两者总和相等；数组 1 的每个数都等于数组 2 里若干个数之和，且数组 2 的每个数只能用一次。要把数组 2 不重不漏地分配到数组 1 的每个数下面。这就是多重子集和（multiple subset sum）：把一个数组划分成若干组，每组之和等于另一数组里对应的一个目标。

它是 NP-hard 的，但属于弱 NP-hard：经典子集和有 $O(n \cdot W)$ 的动态规划， $W$ 是目标值。这个复杂度对数值本身是多项式的，对输入位数却是指数的，所以叫伪多项式：数值大到一定程度就不再划算。对账场景的实际数据规模小、可整数化、且保证有解，用整数化加带剪枝的回溯即可毫秒级求解。

本页四节：问题 → 单目标子集和 → 多目标划分 → 工程要点，末尾附一个可粘贴数据的 demo。

1 · 把碎片装进写好目标的盒子

换个直观的说法：把数组 1 的每个数看成一个盒子，盒子上写着它要装到的目标和；把数组 2 的每个数看成一块碎片。任务是把所有碎片分进盒子，让每个盒子里碎片之和正好等于它的目标。

图 1-1 · 一组真实数据配平后的样子：数组 1 是两个目标盒子，数组 2 是二十二块碎片。这正是要让代码自动算出来的结果。

盒子越多、碎片越多，人工试错会指数级变难，而且容易在「多一块、少一块」上对错账。下面两节先解决单个盒子怎么从碎片里凑出目标，再推广到多个盒子一起分。

2 · 单目标子集和

先只看一个盒子：给定目标和一堆碎片，挑出若干块让它们之和恰好等于目标，这就是经典的子集和（subset sum）。做法是回溯：从大到小逐块决定「选入这块」还是「跳过去试下一块」，选了就递归去凑剩下的差额，走不通再撤销。配两条关键剪枝：剩下的碎片总和都不够时直接回退（剩余和剪枝），以及遇到与刚试过的值相同的碎片就跳过（同值去重）。

注 · 穷举、DP 与回溯三条路都能想到，适合本题的只有一条。朴素穷举把碎片的每种取舍全列出来，图 1-1 的数据有 22 块碎片，单一个盒子的子集就有 $2^{22} = 4{,}194{,}304$ 种。经典子集和的 DP 是 $O(n \cdot W)$ ，快，但它只回答「这堆数能不能凑出目标」这个是否问题，而对账要的是具体哪几块分给了哪个盒子；DP 表还原方案本就麻烦，推广到多个盒子同时划分时状态还得跨盒子叠加。回溯则边试边记下「这块给了谁」，配上两条剪枝，在规模小、可整数化、保证有解的对账场景里实测毫秒级。

图 2-1 · 单个盒子的回溯过程：选入、递归、撤销，以及两条剪枝何时触发。可单步推进观察搜索树如何被剪。

从大到小挑是因为大块的可选位置少、最容易把差额卡死，先决定它们能尽早触发剪枝、让搜索树更瘦。图 2-1 里先试最大的 $6$ ，发现剩下凑不出差额，撤销后改用 $5 + 4$ 。

3 · 多目标划分

有了单盒的子集和，多个盒子只是再套一层回溯：把目标也从大到小排，逐个盒子去自由碎片里找一个子集；找到就锁定这些碎片、去装下一个盒子；若后面的盒子装不下了，就把当前盒刚锁定的碎片全部退回，换一种凑法重来——这层叫盒间回溯。因为两边总和相等，只要前面的盒子都装好，最后一个盒子必然自动配平。

图 3-1 · 多个盒子的逐盒求解与盒间回溯。可单步推进观察碎片何时被锁定、何时被整批退回。

警示 · 盒间回溯在实际数据里很少触发：两组数据本就确实能配平，加上目标与碎片都从大到小的贪心顺序，多数情况下逐盒一次就配平。但这层回溯是正确性的兜底，一旦贪心选错它能换条路。

4 · 工程要点

算法本身就上面两节。真正决定能不能取代人工的是几个工程细节，尤其在金额这种小数场景。

浮点直接相加再比较必然出错。金额是十进制小数，二进制浮点存不下，累加会漂移。图 1-1 那组数据就是现成的例子：两侧总和本该相等，浮点直接累加却得到 $61.660000000000004$ 与 $61.66000000000002$ ，差 $1.42 \times 10^{-14}$ ，=== 判定为不等；而先把每个数乘 100 取整成「分」，两侧都是 $6166$ ，严格相等。务必全程用整数运算，最后再除回去。

图 4-1 · 浮点累加的漂移与整数化后的结果对照。可换数据观察漂移出现在第几位。

总和校验是一道几乎零成本的前置检查：两组数整数化后总和必须相等，不相等就直接判定数据有误。人工对账时「多一块、少一块」极难发现，代码第一步就能报出来。图 5-1 的「大数据（有误）」预设正是末尾多复制了一个 0.28，总和校验当场拦下。

建议 · 降序与同值去重是性能关键。目标与碎片都从大到小处理，大块先定位、搜索树更瘦；同一层遇到值相同的碎片只试一次，因为换一个等值的只会得到重复组合。金额数据里常有大量重复的小额，图 5-1 那组 84 块碎片里 0.28 出现 31 次、0.56 出现 12 次；没有同值去重会把等价子集重复搜成千上万遍。

5 · 粘贴数据的 demo

警示 · 图 5-1 的求解器是贪心简化版：每个盒子锁定找到的第一个可行子集，后续盒装不下时会退回，但不为已装的盒改换另一种凑法重搜。因此它 sound 但 incomplete——给出的划分一定正确，但对少数「需要为某个盒子改换子集才能配平」的实例会误报无解。总和相等却提示失败时，未必真的无解。完备求解需在盒间回溯时枚举每盒的全部子集。

图 5-1 · 可粘贴两组数据求划分，逗号、空格或换行分隔皆可。内置两组测试数据、一组总和对不上的大数据（演示校验拦截）及其修正版。

单目标子集和是回溯（选择、递归、撤销）的一个实例，多目标划分在它外面再套一层回溯，工程要点决定它能否真正落地。更系统的回溯与剪枝见搜索 · 回溯 · 剪枝，把「恰好覆盖」做到 $O(1)$ 撤销见 Dancing Links。

6 · 实际应用

财务对账：银行流水与发票拆分，一笔总额对应明细里的哪几笔、汇总数对应分户账里的哪几条，正是本题。

凑数与找零：用面额碎片凑出指定金额（零钱兑换是它的近亲），满减券组合凑门槛。

分配与装箱：把任务或货物按既定容量切分到若干桶，每桶装到指定额度，是多重背包与 bin packing 的近亲。

竞赛与面试：分割等和子集、目标和、火柴拼正方形都是子集和与多重子集和的变体。