题目描述
判断数组能否分成两个和相等的子集。
nums = [1, 2, 3, 4]
总和/目标 = 10 / 5
输出 = true （{1,4} 与 {2,3}）
思路解析
挑子集有 2ⁿ 种，太暴力了。换成 0-1 背包：每个数选或不选，问能不能把「容量 5」恰好装满。用一排布尔标记 dp。
dp[j] 为真表示「能凑出和 j」。dp[0]=真（什么都不选凑出 0）。每来一个数 num，从大到小更新：dp[j] = dp[j] 或 dp[j−num]。目标看 dp[5]。
建表 · dp[0]=✓：表头是目标和 0~5。dp[0]=✓（凑 0 肯定行），其余先 ✗。下面逐个数字更新。
用 1：拿数字 1：dp[1] 由 dp[0] 推得 → ✓。现在能凑出 {0, 1}。
用 2：拿数字 2（从大到小更新，避免重复用）：dp[3]=dp[1]→✓、dp[2]=dp[0]→✓。能凑 {0,1,2,3}。
用 3：拿数字 3：dp[5]=dp[2]→✓！已经能凑出 5（就是 2+3），答案是 true。
结论：看 dp[5]=✓，能分成两个和为 5 的子集，返回 true。（4 还没用就已经成功了）
「每个物品选或不选、容量恰好/不超」就是 0-1 背包。可行性用「或」、计数用「加」、最值用「max」，骨架全一样。
参考代码（Python）
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): # 从大到小
7 dp[j] = dp[j] or dp[j - num]
8return dp[target]复杂度分析
- 时间复杂度：O(n × target) —— n 个数 × 容量
- 空间复杂度：O(target) —— 一维 dp
套路模板
记住骨架：一维 dp、内层容量从大到小。从大到小=每个物品只用一次（0-1）；改成从小到大就是可重复用的完全背包。
Python
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]易错点
- ❌ 内层从小到大 → ✅ 0-1 背包内层从大到小（从小到大会让一个数被重复使用，变成完全背包）
- ❌ 忘了判奇数和 → ✅ 总和为奇数直接 False（奇数不可能平分）
以上文字与上方动画完全同一思路：先看动画建立直觉 → 读文字巩固 → 关掉页面自己默写一遍代码，能写出来才算真的掌握。