1. 先拆题目：为什么“能否平分”等于“能否凑出半和”

LeetCode 416 这道题，我给不少朋友讲动态规划的时候都会先拿出来当“引子”。它表面上叫“分割等和子集”，看起来像是要把数组分成两堆，但实际上只要把数组总和算出来，再把问题转换一下，难度会瞬间下降一个量级。题目描述不长：给你一个只包含正整数的非空数组，问能不能把它拆成两个子集，让两个子集的元素和相等。注意这里的“子集”指的是从原数组里挑若干个元素，每个元素只能用一次，不要求连续，顺序也不重要。

先做一个最朴素的推导：如果两个子集的元素和相等，都等于某个值 S，那么整个数组元素和就是 2S，必然是个偶数。反过来说，只要数组总和是奇数，就不可能分成两个和相等的整数子集。所以我拿到题的第一时间就会先把总和算出来，做一次(sum & 1) == 1的奇偶判断，这一刀切掉一半的无效输入。顺便再提炼一下接下来的目标：既然两边相等，那么每一侧的和必然是整个数组总和的一半，记作target = sum / 2。于是原问题就变成了“从 nums 中挑出若干个元素，能不能刚好凑出 target”。只要能凑出 target，剩下的元素自然就是另一侧等和子集。

这里面还有一层很容易漏掉的判断：如果数组里某个元素本身就大于 target，那可以直接返回 false。为什么？因为所有元素都是正整数，任何包含这个元素的子集，其元素和至少等于这个元素本身，已经超过 target 了，不可能成为和为 target 的那一侧。这个边界条件在题目给的数据范围下不一定频繁触发，但写上去可以让代码更健壮，也能让思维更完整。下面把这段判断整理成第一步的大纲：

• 求总和 sum；
• sum为奇数直接 false；
• target = sum / 2；
• 如果max(nums) > target直接 false；
• 剩下的任务转为子集求和可行性判断。

这样一拆，416 就不再是“分割”题，而是一个彻头彻尾的“凑数”题。后面写的所有 DP 代码，目标都只有一个：判断是否存在某个子集的和精确等于 target。

1.1 “凑半和”这个目标为什么是充分的

可能有人会问：我只证明了“能凑出 target”是必要条件，那它是不是充分条件呢？其实这一步是双向成立的。如果我从数组里挑出了一个子集 A，它的元素和等于 target，那么剩下没被挑选的元素组成的子集 B，它的元素和就是sum - target = target。所以说，只要存在一个子集之和为 target，剩下的元素自动也会组成另一个和为 target 的子集。等和分割的答案就是“存在这样一个子集”。

这种转换在动态规划里非常重要，因为它把“两侧同时选择”这个看似复杂的问题，压缩成了“只决策一半”。我们不需要同时维护两边分了多少，只需要关心在总和的一半这个容量下，能不能装满。这种思路以后还会有很多变形，比如把一个数组分成两组，让两组差最小，本质上也是在动态规划里寻找不超过某个容量上界的最优凑法，而不是真的去模拟两组元素来回搬运。

1.2 为什么不能用贪心或者双指针

不少初学者会想：先把数组排个序，然后用双指针从两头夹逼，或者从大到小贪心往 target 里塞，不就能判断了吗？我只能说我最初也踩过这个思路的坑。举一个直观的反例：数组[20, 9, 8, 8, 6, 5, 4]，总和是 60，target 是 30。有效的拆分是[20, 6, 4]和[9, 8, 8, 5]，两边都是 30。但如果用贪心，先拿 20，发现还差 10，接下来往里面塞尽量大的数，会优先塞 9，剩下差 1，可数组里没有 1，于是贪心就宣判失败了。这就是贪心的问题：它只看当前一步能不能塞进去更大的数，却没有能力回溯去检查“刚才不拿 9，改拿 6 和 4 会不会更好”。

双指针的问题和贪心类似。双指针在“两数之和”里很有效，但这里的目标和可能是三个、四个甚至更多元素相加的结果，两个指针无法表达任意长度的子集组合。子集问题本质上是在指数级的组合空间里搜索，如果没有一些聪明的记录方式，暴力枚举到数组长度稍大一点就会爆炸。这也正是动态规划登场的原因：它把所有可能达到的和记录下来，避免重复计算同一个子问题。把“能不能凑出 target”拆成“前几个元素能凑出哪些和”，然后逐层递推，每个状态只算一遍，这就是 416 能高效求解的根本逻辑。

2. 背包化建模：二维 DP 的状态与转移从哪来

一旦接受了“凑半和”的转换，下一步就是建模。这个模型和经典的 0/1 背包本质上是一回事。0/1 背包里，每个物品要么拿、要么不拿，并且只能拿一次；这里每个数组元素要么被选进左侧子集、要么不进左侧子集，也只能决策一次。目标从“在容量限制下使价值最大”变成了“是否存在一个选择方案让重量和恰好等于 target”。所以 416 常常被叫作“恰好装满型 0/1 背包”。

2.1 状态定义：dp[i][j] 表示什么

最标准的二维动态规划定义是这样的：dp[i][j]表示只考虑数组的前 i 个元素时，是否存在某种选择方式，使得选出的元素和恰好等于 j。注意这里的 i 从 0 开始，表示“一个元素都不考虑”；dp 数组的行数是n + 1，列数是target + 1。当 j 等于 0 时，不管考虑几个元素，我们总能通过“什么都不选”达到和 0，所以dp[i][0] = true是自然的初始条件。当 i 等于 0 时，除了dp[0][0]是 true，其他dp[0][j]都应该是 false，因为没有元素可选，不可能凑出任何正数。

写起来大概是这种感觉：

dp[i][j] = dp[i-1][j] // 不选第 i 个元素 或 dp[i-1][j - nums[i-1]] // 选第 i 个元素，且 j 必须足够装下它

这里的“或”很关键，它表示只要任意一种方式可行，状态就是 true。这个转移方程背后的逻辑，和记忆化搜索里“当前元素拿还是不拿”的二分分支是完全一致的，但 DP 用一张表把所有分支的结果都存了下来，不会像递归那样反复对同一个(i, j)状态计算多次。

2.2 从一个具体例子看二维状态表

假设数组是[1, 5, 11, 5]，总和是 22，target 是 11。二维 DP 的表最终会告诉我们dp[4][11]是 true，因为可以选择子集[1, 5, 5]达到 11，剩下的[11]也正好是 11。很多人第一次看这道题会觉得二维表很抽象，其实你只要把每一行理解成一串“当前已经能做到的和”的集合，事情就清楚多了：

每一行在上一行的基础上做两件事：保留旧集合里的所有和；再把旧集合里的每个和都加上当前元素值，形成新的和。这里如果某个新和等于 target，就可以直接宣告成功。二维表的好处是清晰、不容易写错，但它的空间是O(n * target)，当数组长度和总和都偏大时不够经济。因此实际工程和刷题中，绝大多数人会继续把它优化成一维 DP。

3. 滚动数组：从二维压到一维，倒序更新是关键

为什么二维 DP 可以压成一维？因为观察转移方程会发现，计算dp[i][j]时，只依赖dp[i-1][j]和dp[i-1][j - nums[i-1]]，也就是只依赖上一行的数据，完全不需要更早的行。既然第 i 行只由第 i-1 行推出，我们就可以只用一个一维数组，在遍历每个元素时原地更新，更新完之后这个数组就代表“当前考虑过的所有元素的可达和状态”。这就是滚动数组的基本思想。

3.1 一维数组的转移长什么样

一维数组定义成dp[j]，表示“在当前已经处理过的元素范围内，是否存在一种选择方式，使元素和等于 j”。初始时，dp[0] = true，其余全部是 false。每处理一个元素num，我们就尝试让所有可达的和都加上num，于是伪代码变成：

for num in nums: for j in range(target, num - 1, -1): dp[j] = dp[j] or dp[j - num]

dp[j] or dp[j - num]的含义很好理解：dp[j]是不拿当前元素时的旧状态，dp[j - num]是拿了当前元素时，是否能凑出剩下的部分。如果原来就能凑出 j，或者原来能凑出 j-num 再加上当前元素，那么新状态就能凑出 j。

3.2 倒序遍历这个细节，藏着最容易翻车的一个坑

上面代码里最容易被忽略的地方，就是第二层循环必须从target倒着往num走。我见过很多刚刚接触背包问题的同学，把内层循环写成从num到target的正序，结果发现示例能过，换几个测试用例就开始出错。原因其实不复杂：如果正序遍历，当 j 从小到大更新时，dp[j - num]可能已经在当前元素处理过程中被更新过，这会导致当前元素被重复使用。拿num = 2举例，正序跑到j = 4时，dp[2]已经因为当前这个 2 变成了 true，于是dp[4]会基于dp[2]变成 true。这相当于说“我用了同一个 2 两次”，明显违背每个元素只能用一次的限制。倒序遍历则确保在更新dp[j]之前，所有比 j 小的索引还没有被当前元素污染，dp[j - num]仍然是上一轮的结果，也就不会发生重复取同一个元素的问题。

为了直观感受，我们用nums = [1, 2, 4, 5]来演示。这个数组总和是 12，target 是 6，正确答案是 true，因为可以拆成[1, 5]和[2, 4]。倒序更新后的布尔数组如下，T 表示 true，F 表示 false：

可以看到，在处理完 4 之后，dp[6]已经变成 true 了，因为2 + 4 = 6；处理完 5 之后，dp[6]继续保持 true，因为1 + 5 = 6。整个状态表记录的就是这样一个事实：随着可选择的元素越来越多，可达的和集合不断扩展，最终覆盖到 target。

4. 边界剪枝与 DP 初版代码的完整落地

讲完了原理，我直接把可以交付的代码给出来。先用 Java 写一版最典型的实现，因为 LeetCode 日常刷题用 Java 的同学最多。这里面我保留了奇偶判断和最大元素剪枝，也让代码保持简洁：

class Solution { public boolean canPartition(int[] nums) { int sum = 0; int max = 0; for (int num : nums) { sum += num; max = Math.max(max, num); } if ((sum & 1) == 1) { return false; } int target = sum / 2; if (max > target) { return false; } boolean[] dp = new boolean[target + 1]; dp[0] = true; for (int num : nums) { for (int j = target; j >= num; j--) { dp[j] = dp[j] || dp[j - num]; } if (dp[target]) { return true; } } return dp[target]; } }

如果更习惯 Python，逻辑完全一致，只是语法换一下：

def canPartition(nums: list[int]) -> bool: total = sum(nums) if total & 1: return False target = total // 2 if max(nums) > target: return False dp = [False] * (target + 1) dp[0] = True for num in nums: for j in range(target, num - 1, -1): dp[j] = dp[j] or dp[j - num] if dp[target]: return True return dp[target]

这里有个值得说明的小优化：在每个元素处理完之后，我都会顺手检查dp[target]是否已经变成 true，如果是就直接返回。可能有人会担心提前返回会不会漏掉后续元素。其实不会，因为dp[target]一旦变成 true，后面的元素只会通过dp[j] || dp[j - num]保持 true，不可能再把它变回 false。target 的可达性只会单调增加，所以这个提前中止是安全的。

4.1 三个常见翻车点

第一个翻车点是初始化错误。有人会把dp全部初始化为 true，或者忘记给dp[0]赋值 true，结果要么所有和都变成可达，要么和为 0 这个最基础的基准态不存在。dp[0] = true的意义是“空集的和为 0”，这是递推的地基，没有它，第一个元素进来时dp[num]永远无法从dp[0] || ...得到传递。

第二个翻车点是内层循环写成for j in range(num, target + 1)，也就是我前面说的正序。这个坑在写 01 背包类问题时几乎是必考题，面试官也特别喜欢问：“为什么背包问题要倒序遍历？”如果你能把“正序会让当前元素被重复使用”这句话讲清楚，通常这道动态规划题就已经过关一大半了。

第三个翻车点是没有做奇偶判断，或者直接把最大元素剪枝写错。最稳妥的顺序是先算 sum，再判断sum & 1，再算 target。因为如果 sum 是奇数，target 根本不是一个整数，用整数除法得到的sum / 2是错误的。最大元素剪枝也要放在算出 target 之后，如果放在前面则没有意义。

4.2 关于if (dp[target]) return true;的放置位置

我在内层循环结束后加了这个判断，它在语义上很自然。有些写法会把判断写到内层循环里，一旦dp[target]为 true 就跳出当前元素的遍历，这也是可行的。但要注意，写在最外层循环末尾更直观，也不容易因为提前跳出而导致漏掉某些 j 的更新。如果你担心性能，其实两者差别很小，因为大多数情况下 target 会在几次元素处理后就成立，少跑几层循环影响有限。

5. 复杂度、常见疑问与位运算提速

先看复杂度。一维 DP 的时间复杂度严格来说是O(n * target)，对于本题的数据范围n <= 200、nums[i] <= 100，sum 最大是 20000，target 最大是 10000，所以最坏情况下大约200 * 10000 = 2,000,000次布尔运算。空间复杂度则是O(target)，也就是一个长度为 10001 左右的布尔数组，占内存非常小。这个复杂度对力扣的测试数据来说极其轻松，完全没有性能压力。也正因如此，这道题很适合作为初学者理解背包问题的第一课，不用一开始就跟各种复杂的空间优化或者常数优化搏斗。

5.1 状态定义里“当前处理过的元素”到底指什么

有同学在阅读一维代码时会感到困惑：dp[j]到底是表示前几个元素的答案，还是全部元素的答案？准确地说，它表示“已经处理到当前元素为止时，所有可用元素能够凑出的和”。每一轮循环开始前，数组代表上一轮结束后的状态；这一轮循环结束后，数组代表本轮考虑完当前元素之后的状态。所以它不是某个固定前缀的答案，而是一个不断更新的全局状态。理解这一点之后，再去读转移方程就会非常顺：dp[j] = dp[j] || dp[j-num]就是在当前元素“拿或不拿”两种选择之间取或。

5.2 用整数位掩码实现的另一种思路

如果你对位运算比较熟悉，会发现布尔数组的更新本质上就是“集合的平移与合并”。每个位代表一个和是否可达，处理一个元素num，相当于把当前所有可达位向左移动num位，再和原来的集合求并。在支持大整数位运算的语言里，这个思路可以直接写成很短的代码。比如 Python：

def canPartition(nums: list[int]) -> bool: total = sum(nums) if total & 1: return False target = total // 2 mask = (1 << (target + 1)) - 1 bits = 1 for num in nums: bits = (bits | (bits << num)) & mask if (bits >> target) & 1: return True return False

这里的bits是一个大整数，第 j 位为 1 表示“和 j 可达”。bits << num把每个可达和都加上 num，再跟原来的bits做按位或，就完成了一次状态转移。掩码mask的作用是只保留不超过 target 的位，防止整数无限膨胀。这种写法的可读性不如布尔数组，但在一些场景下常数很小，代码也短。

6. 从这套思路延伸出去：416 的相邻题型

做会一道题最好的检验方式，是看它能不能迁移到其他题目上。416 教给你的核心能力，是把“分割”“差异”“目标表达式”等具象问题抽象成“凑半和”“凑某个容量”的背包问题。基于这个能力，你去看下面几类题目时会发现它们其实长得很像。

“目标和”那道题是 416 的计数版。它给你一个数组和一个目标值，要求在元素前添加正负号，使所有元素的代数和等于目标。如果把所有元素和记为 S，设添加正号的元素集合之和为 P，那么P - (S - P) = target，化简得到2P = target + S。只要target + S是偶数，就能转成“从数组中挑选元素，使和等于 P”，只不过这次要算的不是“是否存在”，而是“一共有多少种方案”。于是转移方程从dp[j] = dp[j] || dp[j-num]变成dp[j] += dp[j-num]。如果你 416 的推导过程吃透了，做目标和只会觉得顺理成章。

“最后一块石头的重量 II”则是 416 的“最优近似”版。题目的碰撞过程最后等价于把石头分成两堆，让两堆重量差尽量小。我们取总和的一半作为容量上界，用同一个布尔 DP 去维护“不超过这个上界的最大可达和”，最后答案就是sum - 2 * maxReachable。这道题从表面看是一道模拟题，但内里就是 416 的背包建模。

至于“划分为 k 个相等的子集”，我个人不推荐刚学完 416 就直接硬啃。它从分成两组泛化成了分成 k 组，看似只是把目标数量翻了几倍，但状态复杂度完全是另一个量级，常用的解法是回溯加状态压缩，已经远超简单背包的范畴。先通过 416 把两组版的背包思想稳住，再往 k 组版延伸，会平滑很多。

我实际写题时的个人习惯是：拿到数组先算 sum，立刻在心里冒两个分支——奇数直接排掉，最大值超过半和也直接排掉。剩下大概率就是一个背包问题。这种条件反射不是天生的，是反复做类似题目之后形成的肌肉记忆。如果你正在刷动态规划，我建议你手动把 416 的二维 DP 表推导一遍，再改成一维，再写一遍位掩码版本，每个版本都跑过示例。这三种写法都过一遍之后，你对 01 背包“每个物品一次、倒序更新”的理解会深很多，下次碰到任何恰好装模型，都会比只看别人题解要稳得多。