题目描述
思路解析
一句话答案：LeetCode 416 分割等和子集的标准解法是 0-1 背包动态规划：先把「分成两个等和子集」翻译成「能否从数组里挑一些数凑出总和的一半」，总和为奇数直接返回 false；再用布尔 dp[w] 表示能否凑出和 w，每个数只能用一次，容量倒序更新。时间 O(n·target)、空间 O(target)，target 为总和的一半。
分割等和子集为什么等价于凑出总和的一半
题目给一个正整数数组 nums，问能不能把它分成两个子集，让两边元素和相等。直接想「怎么分两堆」会很乱，先做一步翻译：两个子集和相等，每一份必然恰好是总和 sum 的一半；反过来，只要能挑出一些数凑出 sum/2，剩下的数自动构成另一半。于是问题变成判定题：能否选出和恰好等于 sum/2 的子集。
这一步还送一个提前剪枝：sum 是奇数时一半不是整数，正整数无论怎么选都凑不出，直接返回 false。以 nums=[1,2,3,4] 为例，sum=10、目标是 5，{1,4} 和 {2,3} 各凑 5，答案为 true。
为什么这是一个 0-1 背包问题
「从 n 个数里挑一些、每个至多用一次、凑出目标和」正是 0-1 背包的判定版：每个数是一件物品，体积就是数值本身，容量是 sum/2，只关心能不能装满。暴力枚举所有子集是 2 的 n 次方种，指数爆炸。
关键观察是：面对一个新的数 x，任何一种凑法要么用了 x、要么没用。没用时，能凑出哪些和与之前完全一样；用了时，能凑出 w 当且仅当之前能凑出 w - x。「前若干个数能凑出哪些和」这一份信息，足以推出加入下一个数后的全部答案，不必记住具体选了谁——这就是动态规划能压缩指数级搜索的原因。
dp 数组怎么定义，dp[0] 为什么必须是 true
定义布尔数组 dp，dp[w] 表示：用目前已考虑过的数，能否凑出和恰好为 w。初始只有 dp[0]=true——空集的和就是 0，其余全是 false。每加入一个数 x，转移是 dp[w] = dp[w] or dp[w - x]：前者对应不选 x，后者对应选 x、看之前能否凑出 w - x。
dp[0]=true 绝不能漏，它是所有递推的种子：一个数 x 能单独凑出 x，正是靠 dp[x - x] = dp[0] 传导出来的。写成 false，整张表永远推不出任何 true。
一维数组为什么必须倒序更新容量
用一维数组滚动时，内层循环必须让容量 w 从大到小（从 target 减到 x）。原因在于：算 dp[w] 时引用的 dp[w - x] 必须是还没被当前这个数更新过的旧值，代表「不含 x 的历史状态」；倒序扫描时小容量还没被碰过，引用到的正是旧值。
如果正序更新，dp[w - x] 可能已被本轮的 x 更新过，再拿它推 dp[w] 等于把同一个数用了两次——那是完全背包的语义，会把「凑不出」误判成「凑得出」。倒序这一个方向，就是「每个数只能用一次」在代码里的全部体现。
复杂度怎么算，哪些边界容易翻车
时间复杂度 O(n·target)：n 个数，每个数把容量从 target 到自身扫一遍，target 是总和的一半。空间 O(target)，一维布尔数组即可。这是和数值大小挂钩的伪多项式复杂度。
三个高频翻车点：忘了先判总和奇偶；一维数组正序更新，悄悄变成完全背包；漏掉 dp[0]=true 这个空集起点。另外题目保证正整数，若元素可能为负，容量非负的背包框架不再适用，需改用可达和集合等写法。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
下面用一张二维表逐格填，行=数一个个加入，列=要凑的容量。
第 0 行：一个数都还没用。只有容量 0 可行（什么都不拿），其余全不可行。
加入数 1，容量 0 比 1 还小，放不进，只能照搬上方 dp[0][0]=可行。
两条路只要有一条通就可行 → dp[1][0]=✓。
加入第 1 个数 1，看容量 1：不选它=看上方 dp[0][1]=不行；选它=看 dp[0][0]=可行（先腾出 1 的位置）。
两条路只要有一条通就可行 → dp[1][1]=✓。
加入第 1 个数 1，看容量 2：不选它=看上方 dp[0][2]=不行；选它=看 dp[0][1]=不行（先腾出 1 的位置）。
两条路都走不通 → dp[1][2]=·，凑不出 2。
加入第 1 个数 1，看容量 3：不选它=看上方 dp[0][3]=不行；选它=看 dp[0][2]=不行（先腾出 1 的位置）。
两条路都走不通 → dp[1][3]=·，凑不出 3。
加入第 1 个数 1，看容量 4：不选它=看上方 dp[0][4]=不行；选它=看 dp[0][3]=不行（先腾出 1 的位置）。
两条路都走不通 → dp[1][4]=·，凑不出 4。
加入第 1 个数 1，看容量 5：不选它=看上方 dp[0][5]=不行；选它=看 dp[0][4]=不行（先腾出 1 的位置）。
两条路都走不通 → dp[1][5]=·，凑不出 5。
加入数 2，容量 0 比 2 还小，放不进，只能照搬上方 dp[1][0]=可行。
两条路只要有一条通就可行 → dp[2][0]=✓。
加入数 2，容量 1 比 2 还小，放不进，只能照搬上方 dp[1][1]=可行。
两条路只要有一条通就可行 → dp[2][1]=✓。
加入第 2 个数 2，看容量 2：不选它=看上方 dp[1][2]=不行；选它=看 dp[1][0]=可行（先腾出 2 的位置）。
两条路只要有一条通就可行 → dp[2][2]=✓。
加入第 2 个数 2，看容量 3：不选它=看上方 dp[1][3]=不行；选它=看 dp[1][1]=可行（先腾出 2 的位置）。
两条路只要有一条通就可行 → dp[2][3]=✓。
加入第 2 个数 2，看容量 4：不选它=看上方 dp[1][4]=不行；选它=看 dp[1][2]=不行（先腾出 2 的位置）。
两条路都走不通 → dp[2][4]=·，凑不出 4。
加入第 2 个数 2，看容量 5：不选它=看上方 dp[1][5]=不行；选它=看 dp[1][3]=不行（先腾出 2 的位置）。
两条路都走不通 → dp[2][5]=·，凑不出 5。
加入数 3，容量 0 比 3 还小，放不进，只能照搬上方 dp[2][0]=可行。
两条路只要有一条通就可行 → dp[3][0]=✓。
加入数 3，容量 1 比 3 还小，放不进，只能照搬上方 dp[2][1]=可行。
两条路只要有一条通就可行 → dp[3][1]=✓。
加入数 3，容量 2 比 3 还小，放不进，只能照搬上方 dp[2][2]=可行。
两条路只要有一条通就可行 → dp[3][2]=✓。
加入第 3 个数 3，看容量 3：不选它=看上方 dp[2][3]=可行；选它=看 dp[2][0]=可行（先腾出 3 的位置）。
两条路只要有一条通就可行 → dp[3][3]=✓。
加入第 3 个数 3，看容量 4：不选它=看上方 dp[2][4]=不行；选它=看 dp[2][1]=可行（先腾出 3 的位置）。
两条路只要有一条通就可行 → dp[3][4]=✓。
加入第 3 个数 3，看容量 5：不选它=看上方 dp[2][5]=不行；选它=看 dp[2][2]=可行（先腾出 3 的位置）。
两条路只要有一条通就可行 → dp[3][5]=✓。
加入数 4，容量 0 比 4 还小，放不进，只能照搬上方 dp[3][0]=可行。
两条路只要有一条通就可行 → dp[4][0]=✓。
加入数 4，容量 1 比 4 还小，放不进，只能照搬上方 dp[3][1]=可行。
两条路只要有一条通就可行 → dp[4][1]=✓。
加入数 4，容量 2 比 4 还小，放不进，只能照搬上方 dp[3][2]=可行。
两条路只要有一条通就可行 → dp[4][2]=✓。
加入数 4，容量 3 比 4 还小，放不进，只能照搬上方 dp[3][3]=可行。
两条路只要有一条通就可行 → dp[4][3]=✓。
加入第 4 个数 4，看容量 4：不选它=看上方 dp[3][4]=可行；选它=看 dp[3][0]=可行（先腾出 4 的位置）。
两条路只要有一条通就可行 → dp[4][4]=✓。
加入第 4 个数 4，看容量 5：不选它=看上方 dp[3][5]=可行；选它=看 dp[3][1]=可行（先腾出 4 的位置）。
两条路只要有一条通就可行 → dp[4][5]=✓。
看最右下角 dp[4][5]=✓：用全部数能凑出 5，所以能平分成两个和为 5 的子集，返回 true。
几个边界自己心算一遍。
两个高频追问。
参考代码
def canPartition(nums): s = sum(nums) if s % 2: return False t = s // 2 dp = [True] + [False] * t for x in nums: for w in range(t, x - 1, -1): dp[w] = dp[w] or dp[w - x] return dp[t]复杂度
- 时间：O(n·target)，n 个数 × 每个数扫一遍容量
- 空间：O(target)，一维滚动数组
易错点
面试追问把动画讲成自己的话
追问为什么能从「分两等和子集」转成「凑出 sum/2」？
追问如果元素可能为负数还成立吗？
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
不同的二叉搜索树
LeetCode 96 · 中等 · 沿着 一维动态规划 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题