分割等和子集

怎样从“nums=[1,5,11,5] 能否平分 sum=22→子集和 11。”推导出 背包 DP · 0/1，并证明每次状态变化都不会漏掉答案？

中心结论：0/1 背包 dp[sum] 可达;等价 subset sum。

给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

1. 每个数组中的元素不会超过 100 2. 数组的大小不会超过 200

在本站主例中，nums=[1,5,11,5] 能否平分 sum=22→子集和 11。

算法最终需要得到或观察：可达 11,true。

直接递归会反复求同一个子问题；动态规划把答案写入状态表并按依赖顺序复用。

暴力方案的价值是确认题意并提供正确性基线。它通常会覆盖所有候选， 但没有保存已经确认的信息，因此同一状态会被重新计算。

1. 1建模把输入翻译成“状态表账本”，明确答案需要观察什么。
2. 2状态只维护 dp 布尔、nums[i]。
3. 3转移每一步按照 0/1 背包 dp[sum] 可达;等价 subset sum。
4. 4收尾读取 可达 11,true。，并复核边界与复杂度。

先写清 dp 状态含义，再推导转移、初值和遍历顺序。

这道题不是为了记住一个组件名称，而是为了让状态具有可解释的语义：dp 布尔、nums[i]。

给定一个非空的数组，其中所有的数字都是正整数。问是否可以将这个数组的元素分为两部分，使得每部分的数字和相等。 这一题是典型的完全背包的题型。在 n 个物品中选出一定物品，完全填满 sum/2 的背包。 `F(n,C)` 代表将 n 个物品填满容量为 C 的背包，状态转移方程为 `F(i,C) = F(i - 1,C) || F(i - 1, C - w[i])`。当 i - 1 个物品就可以填满 C ，这种情况满足题意。同时如果 i - 1 个物品不能填满背包，加上第 i 个物品以后恰好可以填满这个背包，也可以满足题意。时间复杂度 `O( n sum/2 ) = O( n sum)`。

0/1 背包 dp[sum] 可达;等价 subset sum。

执行过程中持续维护：dp 布尔、nums[i]。

正确性依赖以下不变量：dp[j]|=dp[j-num]。

面试时可以压缩为：0/1 背包 O(n·sum)。

落到当前题，执行机制可以压缩为：0/1 背包 dp[sum] 可达;等价 subset sum。每一次更新都必须保持核心不变量，而不是只让样例碰巧得到正确答案。

1. 1题目与输入nums=[1,5,11,5] 能否平分 sum=22→子集和 11。 因为：0/1 背包 dp[sum] 可达;等价 subset sum。
2. 2dp[1] 用硬币 1: 0+1 = 1尝试每种硬币松弛。 因为：完全背包正序枚举容量。
3. 3预测下一步先不要看下一帧——根据当前不变量,预测算法接下来会怎么动。 因为：主动预测会暴露你对不变量的真实理解,比被动看动画有效得多。
4. 4dp[4] 用硬币 1: 3+1 = 4尝试每种硬币松弛。 因为：完全背包正序枚举容量。
5. 5dp[5] 用硬币 5: 0+1 = 1尝试每种硬币松弛。 因为：完全背包正序枚举容量。
6. 6dp[7] 用硬币 1: 2+1 = 3尝试每种硬币松弛。 因为：完全背包正序枚举容量。
7. 7无法凑出返回 dp[amount]。 因为：O(amount·|coins|)。
8. 8收尾与复杂度可达 11,true。 因为：时间 O(n) · 空间 O(1)。0/1 背包 dp[sum] 可达;等价 subset sum。

代码窗口不会按容易漂移的固定数字行号硬绑动画，而是根据当前语义阶段， 在完整 Go 实现中定位选择、计算、写回或返回分支。当前变量与高亮行一起变化。

func canPartition(nums []int) bool {
	sum := 0
	for _, v := range nums {
		sum += v
	}
	if sum%2 != 0 {
		return false
	}
	// C = half sum
	n, C, dp := len(nums), sum/2, make([]bool, sum/2+1)
	for i := 0; i <= C; i++ {
		dp[i] = (nums[0] == i)
	}
	for i := 1; i < n; i++ {
		for j := C; j >= nums[i]; j-- {
			dp[j] = dp[j] || dp[j-nums[i]]
		}
	}
	return dp[C]
}

func main() {
    // 1. 主例
    //    输入：mode="coin-change", coins=[1,5,11,5], amount=11
    //    期望：可达 11,true。
    //
    // 2. 失败 / 未命中
    //    检查：sum 奇数直接 false。
    //
    // 3. 边界
    //    空输入、单元素、最小合法规模，以及答案恰好落在边界的情况。
    //
    // 4. 迁移
    //    LC494 目标和；LC322 零钱
}

Go 参考实现基于 halfrost/LeetCode-Go 的 MIT 许可代码整理，并按本站教学结构补充解释与动画映射。

1. 1题意nums=[1,5,11,5] 能否平分 sum=22→子集和 11。
2. 2重复直接递归会反复求同一个子问题；动态规划把答案写入状态表并按依赖顺序复用。
3. 3优化0/1 背包 dp[sum] 可达;等价 subset sum。
4. 4证明dp[j]|=dp[j-num]。
5. 5复杂度时间 O(n)，空间 O(1)