题目描述
判断数组能否分成两个和相等的子集。
思路解析
挑子集有 2ⁿ 种，逐个算和再看是不是 11，指数级爆炸。痛点在于：很多子集只是差一个数，前面累加的和却被从头重算了一遍——同样的部分和被反复求。
为什么能用 0-1 背包？因为每个数只有「选或不选」两种，恰好对应背包里物品取一次。用一排布尔 dp[j] 记「能不能凑出和 j」：dp[0]=真（什么都不选就是 0）。每来一个数 num，从大到小扫容量更新 dp[j] = dp[j] 或 dp[j−num]——把「凑过的和记下来，不重算」。最后看 dp[11]。
建表 · dp[0]=✓：表头是目标和 0~11，每格是「能否凑出这个和」。dp[0]=✓（凑 0 肯定行，啥都不选），其余先全 ✗。下面把 nums 里的数 1、5、11、5 一个一个拿进来更新。
拿数字 1：拿数字 1，从大到小扫容量。只有 dp[1] 能更新：它的依赖格是 dp[1−1]=dp[0]=✓，于是 dp[1] 变 ✓。现在能凑出的和是 {0, 1}。
拿数字 5 · 大容量先空扫：换数字 5，从大到小先扫到 dp[11]：它的依赖格 dp[11−5]=dp[6]现在还是 ✗，所以 dp[11] 这轮没法变真。dp[10]、dp[9]…一路往下也都因依赖格还空着保持 ✗。继续往小扫，看哪格的依赖格已经是 ✓。
拿数字 5 · 填 dp[6]：换数字 5，从大到小扫。先看 dp[6]：它的依赖格 dp[6−5]=dp[1]=✓，意思是「先凑出 1，再加这个 5」，所以 dp[6] 变 ✓。为什么从大到小？这样 dp[1] 还是「没用过 5」的旧值，保证这个 5 只被用一次。
拿数字 5 · 填 dp[5]：继续往小扫到 dp[5]：依赖格 dp[5−5]=dp[0]=✓（单独选这个 5），dp[5] 变 ✓。这个 5 处理完，能凑出的和扩到 {0, 1, 5, 6}。
拿数字 5 · 负例 dp[3]：负例：扫到容量 3 时，3 比这个数 5 还小，5 根本装不下。这种格子直接沿用原值不动（dp[3] 还是 ✗）——代码里就是内层循环只扫到 num 为止，比 num 小的容量不碰。
拿数字 11 · 命中：拿数字 11，从大到小第一个就是 dp[11]：依赖格 dp[11−11]=dp[0]=✓，相当于「单独选这个 11」就凑满了！dp[11] 变 ✓，目标已经命中。
结论 · 看 dp[11]：看最后一格 dp[11]=✓：能凑出和为 11 的子集，数组可以平分，返回 true。最后那个 5 还没轮到处理就已经成功了。
「每个物品选或不选、容量恰好或不超」就是 0-1 背包。可行性用「或」、计数用「加」、最值用「max」，骨架全一样。
参考代码（Python）
1s = sum(nums)
2if s % 2: return False # 和为奇数直接不行
3target = s // 2 # 目标 = 总和一半
4dp = [False] * (target + 1); dp[0] = True
5for num in nums:
6 for j in range(target, num - 1, -1): # 从大到小，到 num 为止
7 dp[j] = dp[j] or dp[j - num]
8return dp[target]复杂度分析
- 时间复杂度：O(n × target) —— n 个数，每个数扫一遍容量 target
- 空间复杂度：O(target) —— 只用一行长度 target+1 的 dp
套路模板
记住骨架：一维 dp、内层容量从大到小。从大到小=每个物品只用一次（0-1）；改成从小到大就是可重复用的完全背包。
1# 每个物品最多选一次
2dp = [初值] * (W + 1); dp[0] = 基准
3for x in items:
4 for j in range(W, x - 1, -1): # 必须从大到小!
5 dp[j] = 合并(dp[j], dp[j - x]) # 或/加/max
6return dp[W]易错点
- 错误写法：内层 for j in range(num, target+1)（从小到大） → 正确写法：从大到小：range(target, num-1, -1)（从小到大时 dp[j-num] 已经被本轮的 num 更新过，等于一个数被用了多次，凑出 [2] 也能拼出 4，答案变完全背包）
- 错误写法：不先判奇数和就开背包 → 正确写法：总和为奇数时直接 return False（奇数没法平分；不判的话 target = s//2 会向下取整，背到一个错的目标，结果可能假阳性）
以上文字与上方动画完全同一思路：先看动画建立直觉 → 读文字巩固 → 关掉页面自己默写一遍代码，能写出来才算真的掌握。