目录
力扣416. 分割等和子集
难度 中等
给你一个 只包含正整数 的 非空 数组 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
class Solution {
public:
bool canPartition(vector<int>& nums) {
}
};问题解析
先思考能不能将问题转化成自己熟悉的题型：
如果数组能够被分成两个相同元素之和相同的子集，那么原数组必须有下面几个性质：
- 所有元素之和应该是一个偶数。
- 数组中最大的元素应该小于所有元素总和的一半；
- 挑选一些数，这些数的总和应该等于数组总和的一半。
根据前两个性质可以提前判断数组能够被划分。根据最后一个性质，可以发现问题能转化成01背包的模型：
- 数组中的元素只能选择一次。
- 每个元素面临被选择或者不被选择的处境。
- 选出来的元素总和要等于所有元素总和的一半。
其中，数组内的元素就是物品，总和就是背包。那么我们就可以用背包模型的分析方式，来处理这道题。01背包模板中，要记住的是分析问题的模式。用这种分析问题的模式来解决问题。
以某个位置为结尾，结合题目要求，定义一个状态表示：
dp[i][j] 表示：从前 i 个物品中挑选，总体积不超过 j ，所有的选法中，能否凑成总和为 j 这个数。
状态转移方程：
线性 dp 状态转移方程分析方式，一般都是根据最后一步的状况，来分情况讨论：
不选择 nums[i] ：那么是否能够凑成总和为 j ，就要看在前 i - 1 个元素中 选，能否凑成总和为 j。根据状态表示，此时 dp[i][j] = dp[i - 1][j] ; 。
选择 nums[i] ：这种情况下是有前提条件的，此时的 nums[i] 应该是小于等于 j 。 因为如果这个元素都比要凑成的总和大，那选择它就没有意义。那么是否能够凑成总和 为 j ，就要看在前 i - 1 个元素中选，能否凑成总和为 j - nums[i] 。根据状态表示，此时 dp[i][j] = dp[i - 1][j - nums[i]] ;（nums[i] <= j）。
综上，两种情况下只要有⼀种能够凑成总和为 j ，那么这个状态就是 true 。因此，状态转移方程为： if(nums[i - 1] <= j) dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i]] ; else dp[i][j] = dp[i - 1][j] ;
初始化：多加一行一列，方便初始化，第一行表示不选择任何元素，要凑成目标和 j 。只有当目标和为 0 的时候才能做到，因此第一行仅需初始化第一个元素 dp[0][0] = true ; 第一列表示凑成目标和 j = 0，什么都不选即可，所以第一列全为 true，因此初始化时把整个表初始化成 false，再把第一列初始化成 true。
填表顺序：根据状态转移方程，需要从上往下填写每一行，每一个的顺序是任意的。
返回值：根据状态表示，返回 dp[n][target] 的值。 其中 n 表示数组的大小， target 表示要凑成的目标和。
解析代码
class Solution {
public:
bool canPartition(vector<int>& nums) {
int sum = 0;
for(auto& e : nums)
{
sum += e;
}
if(sum % 2 == 1) // 如果是奇数直接返回false
return false;
int target = sum / 2, n = nums.size();
vector<vector<bool>> dp(n + 1, vector<bool>(target + 1, false));
for(int i = 0; i <= n; ++i)
{
dp[i][0] = true;
}
for(int i = 1; i <= n; ++i)
{
for(int j = 1; j <= target; ++j)
{
if(nums[i - 1] <= j)
dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i - 1]];
else
dp[i][j] = dp[i - 1][j];
}
}
return dp[n][target];
}
};滚动数组优化代码
背包问题基本上都是利用滚动数组来做空间上的优化：（时间也有常数的优化）
- 利用滚动数组优化。
- 直接在原始代码上修改。
在01背包问题中，优化的结果为：
- 删掉所有的横坐标。
- 修改一下 j 的遍历顺序。
（滚动数组优化代码只需能在原代码上修改就行，不用考虑什么状态表示）
class Solution {
public:
bool canPartition(vector<int>& nums) {
int sum = 0;
for(auto& e : nums)
{
sum += e;
}
if(sum % 2 == 1) // 如果是奇数直接返回false
return false;
int target = sum / 2, n = nums.size();
vector<bool> dp(target + 1, false); // 滚动数组优化
dp[0] = true;
for(int i = 1; i <= n; ++i)
{
for(int j = target; nums[i - 1] <= j; --j)
{
dp[j] = dp[j] || dp[j - nums[i - 1]];
}
}
return dp[target];
}
};
