subset-sum · 划分 / 对账

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

一个真实的对账问题：有两组数，数组1 与 数组2，它们的总和相等；数组1 的每个数，都等于数组2 里若干个数之和，且数组2 的每个数只能用一次。要把数组2 不重不漏地分配到数组1 的每个数下面——过去靠人工对，现在想用代码取代。这就是 多重子集和 (multiple subset sum)：把一个数组划分成若干组，每组之和等于另一数组里对应的一个目标。它理论上是 NP-hard，但实际数据规模小、可整数化、保证有解，用 整数化 + 带剪枝的回溯 即可毫秒级求解。全文四节：问题 → 单目标子集和 → 多目标划分 → 工程要点，末尾附一个可直接粘贴两组数据的上手 demo。

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

换一个直观的说法：把数组1 的每个数看成一个盒子，盒子上写着它要装到的目标和；把数组2 的每个数看成一块碎片。任务就是把所有碎片分进盒子，让每个盒子里碎片之和正好等于它的目标。下面是一组真实数据（数组1 两个数，数组2 二十二块碎片）配平后的样子——这正是要让代码自动算出来的结果：

盒子越多、碎片越多，人工试错会指数级变难，而且容易在「多一块 / 少一块」上对错账。下面两节拆开看代码怎么做：先解决单个盒子怎么从碎片里凑出目标（单目标子集和），再把它推广到多个盒子一起分（多目标划分）。

2 · 单目标子集和：选入 → 递归 → 撤销

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

为什么是回溯 + 剪枝，不是穷举或 DP? 三条路都能想到，但只有一条划算。朴素穷举把碎片的每种取舍全列出来再挑——本页 demo 数组2 有 22 块碎片，单一个盒子的子集就有 2²² ≈ 419 万种，n 再大就彻底不可行。经典子集和的 DP ( $O(n\cdot target)$ ) 快是快，但它只回答「这堆数能不能凑出目标」这个是 / 否问题——好比体检报告只盖一个「正常」章，却不写每项数值；而对账要的恰恰是具体哪几块分给了哪个盒子, DP 表还原方案本就麻烦，推广到多个盒子同时划分时状态还得跨盒子叠加，维度迅速膨胀。回溯则像把碎片一张张往盒子里试：装不成就退回来换一张，边试边记下「这块给了谁」；再配两条剪枝——剩下的碎片加起来都填不满当前盒子就立刻掉头（剩余和剪枝）、刚试过的同额碎片不再重复试（同值去重）——在「规模小、可整数化、保证有解」的对账场景里实测毫秒级，这正是它能取代人工的前提。

为什么从大到小挑？大块的可选位置少、最容易把差额「卡死」，先决定它们能尽早触发剪枝、让搜索树更瘦。本例里先试最大的 6，发现剩下凑不出差额，撤销后改用 5 + 4——这就是回溯在起作用。

3 · 多目标划分：逐盒求子集，盒间再回溯

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

盒间回溯在实际数据里很少触发。因为两组数据本就「有根有据、确实能配平」，加上「目标 / 碎片都从大到小」的贪心顺序，多数情况下逐盒一次就配平、用不着退回上一个盒子重来。但这层回溯是正确性的兜底：一旦贪心选错，它能换条路，保证最终一定找到划分（前提是数据真能配平）。

4 · 工程要点：浮点、降序、去重、总和校验

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

**浮点直接相加比较 · 必错。**金额是十进制小数，二进制浮点存不下，累加会漂移。务必先把每个数 Math.round(x * 100) 化成整数「分」，全程用整数运算，最后再除回去。

总和校验 · 先做这道几乎零成本的校验。两组数整数化后总和必须相等，不相等就直接判定数据有误——这是顺手就能做的一道校验。人工对账时「多一块 / 少一块」极难发现，代码第一步就能报出来（本页下方 demo 的「大数据」预设，正是末尾多复制了一个 0.28，总和校验当场拦下）。

降序 + 同值去重 · 性能关键。目标与碎片都从大到小处理，大块先定位、搜索树更瘦；同一层遇到值相同的碎片只试一次（换一个等值的只会得到重复组合）。金额数据里常有大量重复的小额（一堆 0.28 / 0.56），没有同值去重会把等价子集重复搜成千上万遍，甚至卡死。

5 · 上手 demo：粘贴你的两组数据

把两组数填进去（逗号 / 空格 / 换行分隔皆可），点「匹配」即按上面的算法求出划分。内置三组预设：两组测试数据，以及那组总和对不上的大数据（演示总和校验拦截）和它的修正版。

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

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

6 · 实际应用

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

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

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

竞赛与面试:LeetCode「分割等和子集 / 目标和 / 火柴拼正方形」都是子集和 / 多重子集和的变体。