先说结论分割等和子集的本质不是集合分割而是一个披着数组外衣的背包问题。题目给你一个非空正整数数组让你判断能不能把数组拆成两个子集使得两个子集的元素和相等。一眼看过去大家第一反应是分堆组合或者想用双指针、排序贪心。但实际写过几道题之后你就会发现这题的真正考点是0-1背包的变形考的是你对动态规划状态定义和枚举顺序的底层理解而不是什么花哨的搜索技巧。我最早刷这道题LeetCode 416的时候自己也踩过不少坑。用DFS硬搜超时、用二维dp写对了一提交内存却爆了、改成一维dp后结果死活不对——这些坑我后面都会一个个给你拆开讲清楚。而且只要你真正吃透了这道标准题后面遇到分割等和子集的一堆变种比如分成两个子集差最小、允许负数、变成三维背包、甚至限制子集元素个数你都可以直接套同一套思维模板快速解出来。这篇博文我不会只贴代码我会从为什么这题要用背包来做开始把状态转移方程的来历、dp数组每个格子存储的含义、一位数组为什么必须倒序遍历以及变种题的推导思路全部讲透。1. 从题目到模型为什么分割等和子集会被一眼定位成0-1背包1.1 先手动推导一遍暴力思路看它死在哪里假设数组是[1, 5, 11, 5]我们要判断能否分割成和相等的两个子集。数组总和为22所以目标就是找到一个子集使得它的元素和恰好等于11。这一步是几乎所有解法的共同起点两个子集和相等意味着每个子集的和都是总和的一半。如果总和是奇数直接返回false这一点不需要做任何计算是个一步到位的剪枝。那接下来就引出了最朴素的想法从数组中挑一些元素看能不能凑出11。这本质上是选与不选的组合问题。对于每个元素你有两个选择——放进子集A或者不放进子集A。4个元素就有2^416种组合10个元素就是1024种30个元素就是约10亿种。如果数组长度给到100甚至200暴力枚举直接爆炸。有些人的第一反应是用回溯加剪枝先排序然后从小到大尝试和超过target就剪掉。这个思路在数组元素比较小、target比较小的时候确实能跑比如元素全是1或2的小数值数组搜索树可能不会太深。但题目数据一旦出现大量中等数值元素剪枝几乎无法生效指数级回溯就是死路一条。所以你必须意识到这道题考察的不是怎么枚举而是怎么用数据结构去记忆已经算过的子问题。当你看到选与不选凑目标值每个元素只能用一次这三个特征同时出现时这就是0-1背包的标准特征和背包问题的映射关系如下数组元素值 - 物品重量也是物品价值总和的一半target - 背包容量能否恰好装满背包 - 判断问题1.2 为什么不能用排序 双指针很多人拿到这道题第一反应是排序然后两边夹逼。这确实是一个很容易踩进去的思维误区我必须单独拿出来说。你可能会想既然要分成两个和相等的子集那我排个序每次从大的往小的凑凑不出来就换下一个听起来很贪心但实际上是错的。我举个反例[3, 3, 2, 2, 2]。总和是12target6显然可以分割为[3, 3]和[2, 2, 2]。但是如果你用贪心双指针从最大的3开始凑6你会尝试 33 得到一组剩下[2,2,2]另一组这刚好是正确答案看起来没问题。那我换一个数组[6, 5, 5, 2, 2]总和20target10正确答案是[6,2,2]和[5,5]。但贪心会怎么走先从最大元素6开始尝试找4来凑10数组里没有4于是把6丢进去再看55510成功了剩下的[6,2,2]和也是10居然也对了。看起来又没问题这就说明靠几个例子是验证不了贪心的。真正一击致命的反例是[5, 4, 4, 3, 3, 3]总和22target11。贪心先从5开始找6没有接着把5放下取49再取312——超了这个组合回溯的话复杂度就开始上去了。但你拿DFS直接手算会发现正确答案是[5, 3, 3]和[4, 4, 3]贪心如果一味优先放最大元素会很容易走进死胡同再去回溯效率并不比暴力好多少。根本原因在于局部最优的选取策略无法保证全局能够凑满target因为这道题没有贪心选择性质。排序双指针能解决的场景是连续子数组分成两段或者两个数凑target这类约束极强的问题而分割等和子集是任意挑选子集挑选顺序不影响最终和但你无法通过一次顺序扫描就锁定哪些元素属于哪个子集。所以认清这一点之后你才会老老实实去用背包。1.3 这题的变种到底在变什么既然标题是分割等和子集变种我先在这里把变种的维度梳理清楚后面再逐个展开解法。我打过的变种题里主要分这几类总和奇偶性骗局型有的题目会把数组元素改成包含负数或者总和是奇数也可以比如允许丢弃元素这类题要先重新推导target不能直接套奇数返回false。容量变化型原题是两个子集变种可能变成三个子集、四个子集或者指定其中一个子集必须包含特定元素。价值变化型每个元素被选中后它的价值不等于重量可能权重翻倍、可能依赖前一个元素的状态这时就要重新设计状态dp的含义。统计方案数型从能否凑出变成有多少种凑法这就要把bool dp升级成int dp加法转移。找具体分割方案型不但要判断true/false还要输出具体每个元素属于哪个子集这就需要对dp数组做回溯。只要你能把标准题吃透上面这些变种的共性就一句话判断一个集合中是否能选出若干元素满足某种和为约束的条件本质都是背包。下面我从标准题开始把二维dp到一维dp的推导过程彻底讲明白。2. 二维动态规划先把每个格子的含义刻进脑子里2.1 状态定义是怎么想出来的我们不可能一下子跳到一个dp[j]就能写完代码的程度初学者或者写过一段时间但dp理解不深的人我建议先老老实实从二维开始。把问题重新描述为对于前i个元素下标0到i-1我们能否从中选出若干个元素使它们的和恰好等于j如果能就记为dp[i][j] true如果不能就是false。dp[i][j]这个二维数组的规模是(n1) × (target1)。为什么行是n1因为我们希望dp[0][j]专门表示前0个元素即一个元素都不考虑的情况这是一种惯用的边界写法省去很多下标偏移的麻烦。列是target1因为我们需要从和等于0一直记录到和等于target。状态定义的背后逻辑是利用子问题重叠性。当你考虑前i个元素能否凑出j时你会发现这个问题可以被拆成两个更小的子问题最后一个元素nums[i-1]选还是不选。如果不选问题退化为前i-1个元素能否凑出j如果选问题退化为前i-1个元素能否凑出j - nums[i-1]。这两个子问题的规模都更小而且会被很多更大规模的问题反复使用——这就是记忆化的基础。2.2 转移方程一对一拆解转移方程写出来是dp[i][j] dp[i-1][j] || dp[i-1][j - nums[i-1]]但这个式子千万别死记。我们一行一行拆开看dp[i-1][j]当前这个元素nums[i-1]不选那么前i个元素的凑和问题和前i-1个元素的凑和问题完全一样所以直接继承。dp[i-1][j - nums[i-1]]当前这个元素选那么我还需要在前面i-1个元素中凑出j减去当前元素值之后的剩余值。前提条件是j nums[i-1]否则索引会变成负数。这个方程其实和0-1背包的标准转移是同一个东西。唯一区别是0-1背包的表格里存的是最大价值这里是布尔值。但转移逻辑完全一致正是不选当前物品、要么选当前物品二者取更优。我还想特别解释一下j的含义。有些初学者会问为什么j要从0开始遍历到target不能只记录dp[i][target]吗不能。因为你在算dp[i][target]的时候需要依赖dp[i-1][target - nums[i-1]]而target - nums[i-1]不一定是target所以你被迫需要中间所有可能的和值。这就是动态规划用空间换时间的体现你要把所有可能凑出的和值都记录下来后续才能复用。2.3 二维dp的初始化与完整代码示例初始化分两块dp[0][0] true前0个元素凑出和0这是成立的一个都不选就可以了。dp[0][j] false (j 0)前0个元素不可能凑出正数和这是当然的。此外的格子都是通过转移方程计算出来的不需要预先赋值true。这里有一个小细节也是新手最容易错的地方很多人在初始化时会把dp[i][0]全部设为true。这个语义是对的——无论你考虑前几个元素一个都不选永远是凑出0的合法方案。但实际上如果你严格按转移方程从上到下从左到右计算dp[i][0]会自动通过dp[i-1][0]一路继承成true所以不手动设也可以。不过为了语义清晰我建议显式初始化dp[i][0] true也无妨只是要注意不要把dp[0][j] (j0)误设为true。def canPartition(nums): total sum(nums) n len(nums) if total % 2 1: return False target total // 2 dp [[False] * (target 1) for _ in range(n 1)] dp[0][0] True for i in range(1, n 1): val nums[i - 1] for j in range(target 1): # 默认不选当前元素 dp[i][j] dp[i - 1][j] # 如果能选再做一次或运算 if j val: dp[i][j] dp[i][j] or dp[i - 1][j - val] return dp[n][target]时间复杂度O(n * target)空间复杂度O(n * target)。对于标准题目给出的数组长度和数值范围这个复杂度在时间上是可以过的但空间上有优化空间。我在LeetCode上第一次提交二维版本的时候数据大一点的内存消耗就明显偏高这时候就该进入下一节了。3. 一维滚动数组为什么要倒序遍历这是全篇最重要的细节3.1 从二维到一维的压缩逻辑观察二维转移方程dp[i][j] dp[i-1][j] || dp[i-1][j - val]你会发现第i行的值只依赖第i-1行不会依赖更早的行。这就意味着我们没有必要把整个(n1) × (target1)的表格全部保留只要保留下当前行和上一行就足够了。进一步优化当我们按j从大到小遍历时甚至连上一行都不用单独存只需要一个一维数组dp[j]它就地更新、同时扮演上一行和当前行的角色。我画个简单过程。假设现在处理到第i个元素一维数组dp[j]在更新前代表的是dp[i-1][j]。我们要把它更新成dp[i][j]。如果j从小到大遍历dp[j - val]可能已经被这个元素更新过了它代表的是dp[i][j - val]而不是dp[i-1][j - val]——这就错了因为同一件物品不能重复选。所以必须让j从大到小遍历保证计算dp[j]时dp[j - val]还是旧值即上一行的值。这个解释我相信很多人看过但我还想用一个更直观的类比帮你彻底记住。想象一维数组就是一条从左到右的跑道你要根据前面的旧值来更新当前位置。如果从左往右跑你会踩到已经被自己改写过的地面如果从右往左跑你踩到的永远是还没被改写的旧地面。0-1背包里的每个物品只能用一次你当然需要旧地面。3.2 完整一维代码与逐行注释def canPartition(nums): total sum(nums) if total % 2 1: return False target total // 2 dp [False] * (target 1) dp[0] True for val in nums: # 倒序遍历避免同一个元素被多次使用 for j in range(target, val - 1, -1): dp[j] dp[j] or dp[j - val] return dp[target]这段代码的每一个细节都值得说道说道dp[0] True这个初始化对应的是二维中的dp[0][0] true表示一个元素都不选、凑出和0这是所有计算的基石。内层循环上限是val - 1而不是0因为j val时当前元素根本选不了dp[j] dp[j] or dp[j - val]中的dp[j - val]索引越界没有意义而dp[j] or dp[j]的更新等于没更新所以直接从target循环到val即可。dp[j] dp[j] or dp[j - val]这一段对应了二维方程里的不选和选两种情况的或运算。时间复杂度O(n * target)没变空间复杂度从O(n * target)优化到O(target)。别小看这一步当target达到几万时二维数组可能导致数十MB内存开销一维数组只有几百KB。3.3 进一步优化提前剪枝和最大值剪枝写完上面代码就可以通过标准题了但我打比赛和刷题时还会做两个额外优化让速度再快一截而且在变种题中同样适用。优化一提前break。在每一轮外层循环后检查一下dp[target]是否已经为true。如果是说明目标已经达成直接返回true不用再处理剩余元素。这在数据比较友好的时候能省很多无谓计算。代价只是每次内层循环结束后多一次判断几乎可以忽略我建议默认加上。优化二记录当前能达到的最大和内层循环的上限从target降为curSum。因为处理前i个元素时能凑出的和最多不会超过前i个元素的总和curSum超过curSum的j一定都是false循环它们毫无意义。所以我通常用一个变量curSum来维护当前已处理元素的和每轮外层循环把curSum累加进val然后让内层j从min(target, curSum)倒序循环到val。这两个优化叠加后总循环次数可以从n * target下降不少尤其是当数组元素比较小、分布比较稀疏时效果肉眼可见。我也在一些变种题里见过有的人为了多抠这点常数连取min的耗时都要省直接写成固定上限——但对于面试和一般刷题来说带min的版本可读性和性能最均衡。4. 变种一允许负数元素怎么办4.1 负数元素的引入把target坐标轴推成了双向原题数组元素都是正整数所以总和的一半target一定是正数dp数组下标天然是从0到target的一维正向坐标轴。但如果题目改成允许负数情况立刻变了你在凑某个和j的过程中可以选择一个负数元素这会让你当前的和值变小于是你不仅要记录比j小的状态还要记录比j大的状态吗并不是。我们需要回到问题本身目标仍然是能否将数组分成两个子集使得两个子集元素和相等。设整个数组总和为sum其中可能既有正数也有负数。目标子集和为S则另一个子集和为sum - S要求S sum - S于是S sum / 2。注意如果sum是奇数依然返回false如果sum是偶数target依然是一个具体数值。负数没有改变等和分割的目标值推导方式。问题出现在dp数组下标的偏移。因为这题元素可正可负你在凑target的过程中中间状态的当前和可能是负数。比如数组[3, -1, ...]你要凑target4先从3开始累加再减去1中间会出现和值2不会小于0但如果元素是[-5, 8]target3先选-5当前和是-5这就是负数中间状态。解决办法是加偏移量。设所有负数元素绝对值之和为negSum把dp数组的下标整体向右平移negSum这样原本的和值0落在下标negSum处和值的最小可能值-negSum落在下标0处和值最大可能值映射到negSum maxPossibleSum。转移时下标要同时加减偏移。核心代码框架长这样def canPartitionWithNegatives(nums): total sum(nums) if total % 2 ! 0: return False target total // 2 neg_sum sum(-x for x in nums if x 0) offset neg_sum # 我们需要考虑的目标下标是 target offset dp [False] * (target 2 * neg_sum 1) dp[offset] True for val in nums: # 正数和负数的遍历方向相反这点很重要 if val 0: for j in range(len(dp) - 1, val - 1, -1): dp[j] dp[j] or dp[j - val] else: # 负数表示加上val反而减少下标为了避免重复使用需要正向遍历 for j in range(0, len(dp) val): # 注意 val 是负数所以 len(dp)val 是最大有效下标 dp[j] dp[j] or dp[j - val] return dp[target offset]负数情况下遍历方向反过来原因和一维背包的倒序逻辑一样如果val是负数从左往右更新时dp[j - val]对应的下标比j大已经可能被本轮更新过如果从右往左更新dp[j - val]才可能拿到的是旧值。这一层光是文字可能不好理解我建议你拿[2, -1]手工模拟一遍就能彻底明白。4.2 负数变种的一个隐蔽坑target可能是负的吗total是奇数就返回false这个判断在负数数组里依然成立。但要注意如果数组总和是一个负数偶数比如[-2, -4]target -3是不对的我们单独算一下总和是 -6target -3两个子集和都是 -3 才行。[-2, -4]能凑出 -3 吗不能。但如果你直接把target当成数组下标用target -3就会导致下标越界。所以正确做法是不管target是正还是负都统一加上offset再作为下标访问。只要target offset落在dp数组定义域内判断逻辑不受影响。另外total % 2在Python中对负数取余要小心。-3 % 2 1但-4 % 2 0这个结果是对的。不过在某些语言里负数取余行为不一致建议统一写成total % 2 ! 0来判断是否能整除2而不要依赖具体语言的正负号取余规则。5. 变种二统计分割方案数、输出具体方案5.1 从bool dp升级到int dp的转移变化如果题目从能否分割变成有多少种分割方式dp数组的存储内容就要从布尔值升级成整数。dp[j]的含义变成前i个元素中能够凑出和j的方案数。转移方程变成dp[j] dp[j] dp[j - val]这里的加法和bool版的或运算一一对应bool版中不选和选两种情况只要有任意一种成立就行计数版中两种情况的方案数要加起来。初始化时dp[0] 1表示凑出和0只有一种方案——一个都不选。一个常见的坑是方案数会非常大题目如果要求取模一定要记得在每个加法操作后取模否则Python虽然不会溢出但数值变得巨大之后运算速度会显著下降Java/C更是会直接WA。5.2 变种如果两个子集交换顺序算不算同一种方案这个坑我在一个笔试题里遇到过。原题问有多少种方式把数组分成两个和相等的子集有的同学算出的方案数是正确答案的两倍。原因很简单[1, 5, 11, 5]中子集A选[1, 11]和子集B选[5, 5]与子集A选[5, 5]、B选[1, 11]在分割方式中是同一种但在从数组中挑出一个和等于target的子集时会被算两次。解题策略如果你只是统计能凑出target的子集个数不考虑子集属于A还是B那算出来的方案通常是真实分组方案的两倍。想得到真正的分组方案数最后除以2即可或者你从一开始就固定某个元素必须属于A子集再统计其余元素凑出target - 固定值的方案数也能避开重复计数。5.3 输出具体分组方案的dp回溯法有时候题目不仅问能不能分还要求你输出其中一种分组结果。这个需求比单纯的bool判断要多一步先构建二维dp记录路径再倒推。一维dp在压缩空间的同时丢失了路径信息所以这里乖乖用二维bool数组。做法是在dp[i][j]为true时额外记录一个choice[i][j]标记这个true是从不选继承上一行来的还是从选取j-val来的。然后从dp[n][target]往回倒推如果choice[i][j]是不选说明当前元素不属于子集Ai--j不变。如果choice[i][j]是选说明当前元素属于子集A放入结果列表i--j - nums[i-1]。有一点要格外注意当dp[i-1][j]和dp[i-1][j-val]都是true时选择选还是不选会得到不同的分组方案两个都是合法答案。所以如果你只需要输出任意一种随便选一条路径即可如果你要求输出所有方案这里就要递归分叉复杂度也会相应上升。6. 常见问题与排查技巧我在写这题过程中踩过的坑6.1 为什么我的一维dp结果是错的而二维dp是对的最经典的问题就是遍历顺序。开头我花大篇幅讲了一维必须倒序但很多人看完就忘或者写的时候手一滑写成了正序。一个快速自检的方法就是手动运行一个只有两个相同元素的用例[1, 1]target1。正序遍历的话第一个1会把dp[1]置为true第二个1又会在同一轮里基于dp[0]把dp[1]保持true看起来没问题但换成[1, 1, 1]target1正序遍历时第一个1置true第二个1还是基于dp[0]置true你再试试target2显然只有一个1凑不出2但如果正序遍历dp[2]是被第二个1从dp[1]推出的而dp[1]已经被当前元素改成true了于是dp[2]被误判为true——这就是同一物品被用了两次的典型症状。排查技巧任何0-1背包问题你看到结果偏大本不该凑出的和却返回true优先怀疑遍历方向。6.2 为什么我的二维dp数组内存总是超限数据范围一大n * target可能高达几亿个布尔值。比如n 200nums[i]最大到1000target最大可能到100000二维数组就是200 * 100001个布尔在Python里一个bool实际占用远超1字节内存轻松崩掉。解决办法有两个方向使用一维滚动数组这是最推荐的做法空间降到O(target)。如果连O(target)都觉得大因为target本身是一个几个亿的数那你可能不该用常规dp而该考虑用位集bitset优化。见下一节。6.3 位集bitset优化用一长串二进制位当dp数组位集优化是我非常喜欢的一个技巧尤其是在做变种题和笔试题时它能把常数降到极低。思路是用一个整数的二进制位来表示dp数组中哪些和值是可达的。第j位是1表示当前能凑出和j。初始时只有第0位是1每处理一个元素val就相当于执行一次左移和或运算dp dp | (dp val)这里dp val表示把所有可达的和值整体加上val产生新的可达和dp | 这个结果表示不选或选当前的元素。由于我们只有这一条语句对一个元素只会做一次左移和或操作天然不会重复使用同一个元素所以根本不需要纠结正序倒序问题。Python里的整数是无限长的直接用就行def canPartitionBitset(nums): total sum(nums) if total % 2: return False target total // 2 dp 1 # 第0位为1 for val in nums: dp | dp val # 检查 target 位是否为1 return (dp target) 1 1这段代码在处理大target时依然很快因为位运算本身是高度优化过的而且Python大整数的位长度可以非常高。我在本地实测过nums长度几百、target几万的用例位集版本比普通一维dp通常能快几倍到十几倍代码量更是少得感人。不过它也有缺点你很难从位集中直接提取具体方案只能做bool判断以及位集的空间复杂度虽然压缩到了target/word_size但如果你要统计方案数而不是判断可达性位集就帮不上忙了。6.4 特殊情况速查表这些输入我一秒钟就能给出答案输入特征结论原因总和为奇数直接false偶数求和无法被平分数组只有一个元素直接false除非元素为0分不出两个非空等和子集有元素大于target不可能凑出target直接false但注意要排除负数情况正整数大于目标和肯定不能选最大元素等于target且其余元素总和也等于targettrue天然分成两个子集数组元素全是相同值x长度为n当n * x为偶数且能组成(n*x/2)/x个元素时true本质是看能否用若干个x凑出目标存在负数元素不能简单返回false需要加偏移量处理负数会改变中间和值范围这张表是我在实际刷题和笔试中积累的。看到这些输入特征时先走快速判断能避免无谓的dp计算。但要注意只有总和为奇数和单个元素大于target这类强条件是绝对判死的其他特征只是帮你快速定位不能替代完整dp否则会踩空。7. 变种三三维背包、四子集分割、指定容量的组合7.1 三等分子集从一维target变成二维targetLeetCode 698划分为k个相等的子集是分割等和子集的进阶版也是变种题里出现频率很高的一道。当k2时就是标准题但k2时问题从一个背包容量target能否装满变成了k个背包容量target能否同时装满。这是质变不是简单套用原版就行。最朴素的做法是DFS 回溯维护k个桶的当前和逐个把元素放进某个桶里。剪枝技巧决定了这种写法能不能过数组从大到小排序先放大数能大幅减少搜索分支。如果当前元素的值正好能填满某个桶优先放它。如果两个桶当前和相同那么把当前元素放进哪个桶效果等价可以跳过重复分支。但我更建议你从动态规划角度理解k2的版本dp[mask]表示使用mask这个位掩码对应的元素时已经填满的桶数以及当前桶的剩余容量。状态转移时枚举下一个元素看能不能放进当前未满的桶或者新开一个桶。这种写法不良构复杂的是O(2^n * n)当n比较大时依然吃力所以DFS剪枝在实际中往往比mask dp更快。具体到三等分如果题目只要判断能否分成三个和相等的子集可以先用总和判断target total / 3是否为整数然后把问题转换成数组里是否存在两个不相交子集和都为target等价于是否存在一个子集和为target同时剩下的元素里还能再凑target。这个可以通过在一次dp中记录凑出(target, target)的二维bool状态来解决也就是一个目标二元组版本的背包不再赘述直接上状态方程思路dp[j][k]表示当前元素处理完后第一个桶容量消耗为j、第二个桶容量消耗为k是否可行。遍历时对每个元素更新dp[j][k] || dp[j-val][k] || dp[j][k-val]。7.2 限制子集元素个数的变种怎么改如果题目加上两个子集元素个数之差不能超过1或者子集A恰好包含m个元素那你光靠一维dp记录和值就不够用了因为和值相等还不足以保证个数满足要求。这种场景要把dp扩展到二维dp[j][k]表示当前凑出的和为j、已经选择的元素个数为k是否可行。初始化dp[0][0]true转移时同时考虑选或不选更新和的数值和个数计数。这种三维背包的复杂度是O(n * target * n)看字母就知道很昂贵所以实际题目中n一般不会给太大。如果target和n都大那基本不能做只能靠贪心或者数学规律。我在写这类变种时的经验是先看题目数据范围再决定要不要上三维dp。如果n 100target 10000三维dp勉强能跑如果n到了上千果断放弃dp去看有没有贪心或数学解法。7.3 从子集和到多重背包的思维方式分割等和子集一类题的共同思维模板我已经帮你总结成一张流程图式的清单下次遇到新变种可以按顺序走一遍先计算总和确定目标值 target。如果题目允许丢弃元素target不一定等于总和一半要额外读清条件。判断target是否整数不能整除直接返回false或对应题目要求的空结果。判断数据特征都是正数可能有负数需要偏移量吗有没有元素大于target选算法bool判断用位集/一维dp计数用int dp输出方案用二维dp回溯多子集用DFS剪枝或mask dp。定遍历顺序正数元素倒序遍历负数元素正序遍历多维时逐维确认顺序。验证边界total为0、数组为空、只有一个元素、target为0的情况都要单独测一下。这套清单我从LeetCode 416、698、剑指Offer II 101以及一系列笔试变种题里反复验证过基本覆盖了90%以上的子集和问题场景。8. 实际场景延伸分割等和子集在真实工程中的用处也许你会觉得这种题就是刷题用工作中根本用不到。但我可以负责任地告诉你它的思想在好几个工程方向上是直接落地的。第一个场景是资源分配与负载均衡。有一批任务每个任务有预估耗时你要把它们分配给两台机器希望两台机器的总耗时尽量接近——这就是分割等和子集的带权版本。如果任务是能否让两台机器总耗时完全相等那就是本题如果改成最接近就是最小子集差问题思路还是背包但是把bool dp改成计算可达和值后找最接近target的那个值。第二个场景是数据分桶与分片。比如有一堆日志文件要根据大小把它们分为两组使两组总大小尽量均衡方便并行处理。这本质上和上面完全一样。我实际做过一个数据迁移工具把要迁移的表按预估数据量分组两组分别走两条迁移通道就用到了背包思路来尽量均衡。第三个场景是预算分配和组合决策。给你一堆候选项目每个项目有成本问你能否凑出一个恰好等于某预算的集合。这正好是判断能否凑出target的直接应用甚至不需要二等分把target换成指定预算即可。我自己的体会是刷题的价值不在于记住题目本身而在于建立问题特征 - 算法模型的反射。你看到选与不选恰好能否凑出这些字眼能条件反射地想到背包这才是刷这类题的最大回报。最后再分享一个小技巧如果你在笔试中遇到这题的变种时间紧张又不想纠结推导可以先写一个暴力搜索验证小数据再写dp优化大数据写完后用随机数据对比暴力结果和dp结果是否一致。这个对拍方法我每次刷动态规划题都会用能帮你快速发现遍历顺序或状态定义上的错误。分割等和子集这个系列从标准题到负数变种、计数变种、k等分变种本质上都在锻炼同一套思维一旦打通了你会发现自己解背包类题目的速度会上一个台阶。