分割等和子集
给你一个只包含正整数的非空数组 nums。
请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
每个数组元素只能放入其中一个子集，不能重复使用。
示例 1：
输入：nums = [1,5,11,5]
输出：true
解释：数组可以分割成 [1,5,5] 和 [11]。
示例 2：
输入：nums = [1,2,3,5]
输出：false
解释：数组不能分割成两个元素和相等的子集。
提示：
1 <= nums.length <= 2001 <= nums[i] <= 100
动态规划（0-1 背包）：
class Solution {
public:
bool canPartition(vector<int>& nums) {
int total = 0;
for (int num : nums)
{
total += num;
}
if (total % 2 == 1)
{
return false;
}
int target = total / 2;
vector<bool> dp(target + 1, false);
dp[0] = true;
for (int num : nums)
{
for (int j = target; j >= num; j--)
{
dp[j] = dp[j] || dp[j - num];
}
}
return dp[target];
}
};
核心思想
假设数组可以被分成两个和相等的子集，并且数组所有元素的总和是 total。
那么每个子集的目标和必须是：
total / 2
所以原问题可以转换成：
能不能从
nums中选出一些元素，使它们的和恰好等于total / 2？
这就是一个典型的 0-1 背包问题：
- 每个数字相当于一个物品
- 数字的值相当于物品重量
- 背包容量是
target - 每个数字只能选择一次
- 目标是判断能不能恰好装满背包
这题最关键的观察是：
两个子集和相等，当且仅当其中一个子集的和等于整个数组总和的一半。
为什么总和为奇数时一定不可能
如果两个子集的和相等，设每个子集的和为 x，那么总和就是：
total = x + x = 2x
因此 total 一定是偶数。
如果 total 是奇数，就不可能被平均分成两个整数和相等的子集，可以直接返回 false。
例如：
nums = [1,2,3,5]
total = 11
总和是奇数，所以不可能分成两个和相等的子集。
状态定义
定义：
dp[j] 表示从已经处理过的数字中，能否选出一些元素，使它们的和恰好等于 j。
dp[j] == true 表示和 j 可以被凑出。
dp[j] == false 表示目前还不能凑出和 j。
题目要求判断是否能凑出目标和 target，所以最终答案是：
dp[target]
初始化
不选择任何数字时，元素和为 0。
所以：
dp[0] = true
其余状态开始时都不能被凑出：
vector<bool> dp(target + 1, false);
dp[0] = true;
如果没有 dp[0] = true，就无法从空集合开始接上第一个数字。
例如处理数字 5 时，只有当 dp[0] 为 true，才能推出：
dp[5] = true
递推公式推导
现在处理一个数字 num。
对于目标和 j，有两种选择。
1. 不选择 num
如果之前已经可以凑出 j，那么现在仍然可以凑出 j：
dp[j]
2. 选择 num
如果之前可以凑出 j - num，那么加上当前数字 num 后，就可以凑出 j：
dp[j - num]
所以递推公式是：
dp[j] = dp[j] || dp[j - num]
代码中写成：
dp[j] = dp[j] || dp[j - num];
其中 dp[j] 表示不选择当前数字，dp[j - num] 表示选择当前数字。
为什么容量必须倒序遍历
这是本题最容易出错的地方。
每个数字只能使用一次，所以处理 num 时，dp[j - num] 必须是处理当前数字之前的状态。
因此容量要从大到小遍历：
for (int j = target; j >= num; j--)
如果改成从小到大遍历：
for (int j = num; j <= target; j++)
那么当前轮刚刚更新的 dp[j - num] 可能又被拿来更新 dp[j]。
这样相当于在同一轮中重复使用了当前数字，变成了完全背包，而不是 0-1 背包。
例如：
nums = [3]
target = 6
数字 3 只能使用一次，所以不应该凑出 6。
如果从小到大遍历：
- 先由
dp[0]推出dp[3] = true - 再用刚更新的
dp[3]推出dp[6] = true
这就错误地把同一个 3 使用了两次。
倒序遍历时，计算 dp[j] 所依赖的 dp[j - num] 仍然是上一轮的旧状态，因此每个数字最多使用一次。
为什么使用一维数组不会丢失状态
如果使用二维数组，可以定义：
dp[i][j] 表示只使用前 i 个数字时，能否凑出和 j。
二维转移是：
dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i - 1]]
当前状态只依赖上一行，所以可以用一维数组复用空间。
关键仍然是倒序更新。
倒序更新时，dp[j - num] 还没有被当前数字更新，仍然相当于二维数组中的上一行状态。
因此一维数组既能保留正确的状态，又能把空间复杂度从 O(n * target) 降到 O(target)。
正确性证明
我们证明：算法返回 true 当且仅当数组可以被分割成两个和相等的子集。
结论 1：如果总和为奇数，算法返回 false 是正确的
如果数组能被分成两个和相等的子集，设每个子集的和为 x。
那么数组总和一定是：
2x
也就是偶数。
所以当 total 是奇数时，不可能存在这样的分割，算法直接返回 false 正确。
结论 2：dp[j] == true 表示可以从已处理数字中选出若干个，使它们的和为 j
初始时，dp[0] = true，表示不选任何数字可以凑出 0。
其他状态为 false，表示暂时不能凑出这些和。
处理数字 num 时，对每个 j：
- 如果原来
dp[j] == true，说明不选num也能凑出j - 如果原来
dp[j - num] == true，说明选上num后可以凑出j
所以更新：
dp[j] = dp[j] || dp[j - num]
正好覆盖了“不选当前数字”和“选择当前数字”两种情况。
由于容量倒序遍历，dp[j - num] 是当前数字还没参与时的旧状态，因此不会重复使用 num。
所以每轮处理后，dp[j] 的含义都保持正确。
结论 3：如果 dp[target] == true，数组可以分割成两个和相等的子集
dp[target] == true 表示可以从 nums 中选出一些数字，它们的和为 target。
而：
target = total / 2
剩下没有被选中的数字之和就是：
total - target = target
因此选中的数字和剩下的数字可以组成两个和相等的子集。
结论 4：如果数组可以分割成两个和相等的子集，算法一定会令 dp[target] == true
如果存在一个合法分割，那么其中一个子集的和一定是 target。
这个子集由数组中的若干元素组成，并且每个元素只使用一次。
算法按顺序处理所有元素，每个元素都有“选”或“不选”两种状态转移。
根据结论 2，所有能由已处理元素凑出的和都会被正确记录。
所以当所有数字处理完后，这个和为 target 的子集一定会使 dp[target] == true。
得出结论
由结论 1 可知，总和为奇数时算法判断正确。
由结论 2 可知，动态规划状态含义正确。
由结论 3 和结论 4 可知，dp[target] 与能否分割成两个等和子集完全等价。
因此算法正确。
举例理解
以：
nums = [1,5,11,5]
为例。
数组总和是：
22
所以目标和是：
target = 11
接下来问题变成：能不能从数组中选出一些数字，使它们的和为 11。
处理过程可以这样理解：
- 看到
1，可以凑出1 - 看到
5，可以凑出5，也可以凑出1 + 5 = 6 - 看到
11，可以直接凑出11
所以 dp[11] == true。
这说明可以选出子集：
[11]
剩下的数字是：
[1,5,5]
它们的和也是 11，因此返回 true。
再看：
nums = [1,2,3,5]
总和是 11，是奇数。
所以不可能分成两个和相等的子集，直接返回 false。
复杂度分析
设数组长度为 n，数组总和的一半为 target。
外层遍历每个数字，内层遍历容量 target。
所以时间复杂度是：
O(n * target)
一维动态规划数组长度是 target + 1。
所以空间复杂度是：
O(target)