LeetCode 416. 分割等和子集：01 背包的入门与「可行性 DP」

题目与转化：第一步是「识别」

LeetCode 416：给定非空正整数数组，判断能否分割成两个元素和相等的子集。

输入：[1, 5, 11, 5] → 输出：true（[1,5,5] 与 [11]）
输入：[1, 2, 3, 5]  → 输出：false

转化的两步：第一步：和的奇偶性——总和为奇数 → 直接 false（无法均分——「剪枝」先行）；第二步：问题转化——「分成两个相等的子集」=「能否选出子集使其和 = total/2」——「选或不选」的子集选择——这就是 01 背包：每个数字是一件物品（重量=数值）、背包容量 = total/2、问能否「恰好装满」——「识别为背包」是这道题的核心洞察——表面是「分割」，本质是「子集和问题」——「问题转化」的功力：从业务描述到经典模型——「刷题刷的是转化力」。

状态设计：可行性 DP

状态定义：dp[j] = 「能否用已考虑的数字，恰好凑出和 j」——布尔值——「可行性 DP」与「最优化 DP」的区别：本题求「能不能」（布尔）、最优化 DP 求「最优值是多少」（数值——「布尔 DP 的转移」是或运算：dp[j] = dp[j] or dp[j - num]——「或」的语义：j 可凑出 = 不选 num 能凑出（dp[j]）或 选 num 能凑出（dp[j-num]）。初始化：dp[0] = true（「什么都不选凑出 0」——空集的合法性——边界永远从「空」开始）。答案：dp[total/2]。

def can_partition(nums):
    total = sum(nums)
    if total % 2 != 0:
        return False
    target = total // 2
    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]
    return dp[target]

「倒序遍历」：一维背包的核心细节

为什么必须倒序：一维数组 dp[j] 同时表示「本轮处理 num 前后的状态」——正序遍历的灾难：dp[j] = dp[j] or dp[j - num]——正序时 dp[j - num] 是本轮已更新过的——「num 被用了两次」——「每个物品只能选一次」（01 背包的定义）被破坏——倒序时 dp[j - num] 是上一轮的（num 还没处理过）——「每个物品只影响一次」——「倒序保证 01、正序变完全」——「完全背包」（每个物品无限次）恰好用正序——「遍历顺序」不是细节，是算法语义本身——「二维到一维的滚动压缩」：二维 dp[i][j] = dp[i-1][j] or dp[i-1][j-num]——一维复用数组、倒序遍历——「上一轮 vs 本轮」在倒序下自然区分——爬楼梯篇的滚动变量思想在这里的具体化。「记忆口诀」：「01 背包倒着走，完全背包正着走」**——理解了原因（本轮 vs 上轮的区分），口诀就不需要背。

graph TD
    A[转化: 选子集凑出 total/2] --> B[01 背包 可行性 DP]
    B --> C[dp[j] = dp[j] or dp[j-num]]
    C --> D{遍历方向}
    D -->|正序| E[物品被重复使用 ✗]
    D -->|倒序| F[每个物品只选一次 ✓]

剪枝与「可行性 DP」的实战技巧

剪枝一：提前退出。dp[target] == True 时立即返回——「找到了就不用继续」——可行性 DP 的天然剪枝（最优化 DP 没有这个优惠——「可行性 DP 的早停」是它比最优化 DP 快的原因之一。剪枝二：num > target 跳过。单个数字超过 target——「装不下」直接跳过（内层的起点 num - 1 已隐含——「range 的下界」本身就是剪枝——「range(target, num-1, -1)」——num > target 时区间为空——「空区间=自动跳过」的优雅。剪枝三：num == target 直接 True。「单个数字恰好等于 target」——立即返回——「最平凡的解」先查。「可行性 DP 的另一个应用」：「单词拆分」（LeetCode 139——dp[i] 表示前 i 个字符可拆——「拆分 = 选择 = 背包」的又一转化——「『能否』型问题的 DP 通用模式」：布尔数组 + 或运算 + 剪枝早退——「可行性 DP」家族：子集和、单词拆分、组合总和（判断可行）——「最优化 DP」家族：最大子数组、编辑距离、最长子序列——「两个家族」的转移运算不同（or vs max/min）但框架相同。

背包的进阶：完全背包与「背包家族的遍历顺序」

背包家族的进阶：完全背包与遍历顺序的系统总结。「完全背包」：「每个物品可选无限次」——「正序遍历」（dp[j] 依赖本轮的 dp[j-num]——「重复使用」的允许——「01 与完全的对比」（倒序 vs 正序——「一个方向之差」两个语义——「零钱兑换（322）」（最少硬币数——「可行性→最优化」（dp[j] = min(dp[j], dp[j-coin]+1)——「min 的转移」——「零钱兑换 II（518）」（组合数——「组合 vs 排列」（「组合」外层物品内层容量——「排列」外层容量内层物品——「遍历的内外交换」改变语义——「组合数与排列数」的两个经典——「322 与 518」的对比——「同是完全背包、内外交换得到不同答案」——「内外循环的语义」：「外层是物品」=组合（不关心顺序）——「外层是容量」=排列（关心顺序）——「内外交换」的深层理解——「这是背包家族最精妙的细节」。「背包家族的遍历顺序总表」：「01 背包」（二维正序、一维倒序——「01 的一维倒序」——「完全背包」（一维正序——「多重背包」（每个物品限次数——「二进制拆分」（拆成 01 背包——「分组背包」（每组选一个——「三层循环」——「家族的遍历顺序表」：01 倒序、完全正序、多重二进制拆分后倒序、分组两层循环——「遍历顺序表」是背包家族的导航图——「四个家族」的递进难度——「01 → 完全 → 多重 → 分组」——「每一步」引入新的维度。「背包的工程应用」：「资源分配」（预算分配问题——「预算 = 容量、项目 = 物品」——「ROI 的背包」——「依赖安装的取舍」——「磁盘清理」（删哪些文件腾最多空间——「背包在工程的影子」——「算法题是工程问题的抽象」——「抽象的能力」=「建模的能力」。背包的进阶总结：完全背包的正序语义+内外循环交换的组合/排列之差+家族遍历顺序总表+工程的资源分配映射——「背包家族」的掌握标准：「给任何一个资源分配场景，能识别背包类型、写出遍历顺序、说清语义」——**「识别+顺序+语义」三件套——这是背包从「刷题」到「内功」的转变。

分割等和子集的高频问答：正序之祸、位运算优化与 NP 的边界

问题一：内层循环写成从 num 到 target 的正序，实际会怎么错？——物品被重复使用。拿 nums=[3]、target=6 手推：正序时先算 j=3，dp[3] = dp[3] or dp[0] = true；再算 j=6，dp[6] = dp[6] or dp[3] = true——同一个 3 被用了两次，「3+3=6」被凭空凑了出来。倒序时先算 j=6（此刻 dp[3] 还是上一轮的 false）、再算 j=3——每个物品只进入转移一次，语义正确。「遍历方向决定读的是本轮还是上轮」是整个背包家族的核心细节，写错的症状非常统一：答案偏大、物品被暗中复用——排查此类 bug 时第一反应就是查循环方向，它的优先级比查转移方程更高。

问题二：能比 O(n × target) 更快吗？——常数层面能：位运算优化。把布尔数组压进一个大整数的二进制位——第 j 位为 1 表示「和 j 可行」——转移浓缩成一行：bits |= bits << num。「左移 num 位」就是「选了 num 之后新增的可达和」，或运算合并「不选」的旧状态；大整数按位整体移动，天然保证每件物品只叠加一次，连「倒序与否」的纠结都消失了。Python 的大整数让这个写法自然成立；C++ 用 bitset 或手写 uint64 数组，复杂度从 O(n·target) 除以字长 64。面试时写出它并解释「为什么移位等价于转移」是确定性加分项；同时要能说出适用边界：位压缩只适合「可行性」「计数取模」这类布尔或小值域 DP，求最大价值的真背包（值域压不进位）就不行——优化技巧的价值一半在会用，一半在知道什么时候不能用。

问题三：从「分成两份」到「分成 k 份」（LeetCode 698），难度为什么骤增？——因为复杂度等级变了。416 是伪多项式算法：O(n·target) 看似多项式，但 target 是数值不是输入规模——数值翻倍、时间翻倍，所以叫「伪」多项式；它依然是可解的。698「划分为 k 个相等的子集」在 k ≥ 3 时是 NP-hard 的，没有已知多项式算法，主流解法是回溯 + 强剪枝（数组从大到小排序、当前桶恰好装满时跳过同值数字的对称性剪枝、优先填空桶）或状态压缩 DP（O(2ⁿ × k)，n ≤ 16 量级才可做）。两题并排的教训：「分堆」类问题的可解性对 k 极其敏感——看到「恰好平均分成 k 份」就应警觉多项式与指数的分界，先报复杂度等级、再决定写哪类算法，这是面对陌生题的专业姿势，也是这道题超出「背包入门」的延伸价值。

问题四：target 特别大（比如 10⁹）时 dp 数组开不下怎么办？——先做可达和集合化：可行性只关心「能凑出哪些和」，而可达和的数量有限——用 set 或位图存「已可达的和」而不是按 target 开定长数组，规模从值域压到实际可达数，配合「num > target 跳过」的剪枝，实际规模通常远小于理论值。若数值都极大、n 却不大（40 以内），就换折半枚举（Meet in the middle）：前一半的所有子集和、后一半的所有子集和各存一份排序，两两查补数 O(2^(n/2))——「值域大到开数组」与「n 小到可枚举」是两把不同的钥匙，先看哪个维度小，就用哪个维度的算法——这道题从「背包装满了吗」延伸出的最后一课，是复杂度里两个变量的取舍意识。

小结

分割等和子集的完整解析：转化的两步（奇偶剪枝 + 「分割」转「子集凑出 total/2」——「识别为 01 背包」是核心洞察）；可行性 DP（dp[j] 布尔、或运算转移、dp[0]=true 的空集边界）；倒序遍历（「本轮 vs 上轮」的区分——正序破坏「每个物品选一次」——倒序保证 01——「遍历顺序即算法语义」）；剪枝（早退、空区间、单数即中）；家族对照（可行性 or 运算 vs 最优化 max 运算——框架相同、运算不同）。给学习者的进阶路径：01 背包入门（本题）→ 完全背包（零钱兑换）→ 分组背包 → 多重背包——每个变体只改变「物品的选择次数」——「遍历顺序」随之变化（倒序/正序/分层的倒序）——「抓住『每个物品能选几次』这一个变量，就抓住了背包家族的全部脉络——而这道题，就是走进这个家族的第一扇门。

分割等和子集教会的是「转化」：把「均分」翻译成「凑和」、把「凑和」识别成「背包」——算法能力的分水岭，从来不是「会不会写 DP」，是「能不能把陌生问题翻译成熟悉模型」。