给你一个 只包含正整数 的 非空 数组 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
解题思路
我们遇到动态规划的题，一定不能去背状态表示是什么，而是要去摸清楚为什么状态要这么表示，因为动态规划的题变幻莫测，就算你背下了一万个状态表示，也会有第一万零一个状态等着你，所以一定要根据题目来推导状态表示而不是去背！
这道题其实还是比较好推出题目背后隐藏的信息的，虽然题目讲的不像是背包问题，但是我们可以把它变成背包问题！
题意的转换
题目要我们将数组分割成两个子集，其实就是分为两个背包，其中两个背包中的元素和是相等的，那我们其实就可以转化为去求其中一个背包中的元素和是否是数组元素总和的一半！
其次，既然要是能分为两个元素和相等的背包，那么这个数组的元素和必须是个偶数，否则是无法平分的！
总结一下，就可以转化为 01背包 的模型，如下所示：
- 数组中的元素只能选择一次
- 每个元素面临被选择或者不被选择的情况
- 选出来的元素总和要等于所有元素总和的一半
状态表示
根据 “经验 + 题目要求”，可以得到状态表示为 dp[i][j] 表示在前 i 个元素中选择，此时其元素和是否等于 j。
状态转移方程
状态无非就是两种情况，第一种就是不被选择，这种情况比较简单；第二种就是被选择，这种情况我们就得考虑此时元素的大小和背包空间的大小关系！总结起来如下图所示：
初始化
由于需要用到上一行的数据，因此我们可以先把第一行初始化。
第一行表示不选择任何元素，要凑成元素和为 j，只有当元素和为 0 的时候才能做到，因此第一行仅需初始化第一个元素 dp[0][0] = true
而第一列表示背包空间为 0，那么只要我们不选任何元素，此时都能满足，所以总结下来就是初始化第一列元素为 true。
遍历顺序
因为用到了 dp[i - 1][j] 和 dp[i - 1][j - nums[i]]，所以从上往下，从左往右去遍历！
返回值
根据状态表示，返回最后一个元素 dp[n][V]
class Solution {
public:
bool canPartition(vector<int>& nums) {
// 计算出数组中元素总和
int sum = 0;
for(auto e : nums)
sum += e;
// 背包大小不为偶数的话肯定无法分为元素和相等的子集
if(sum % 2 == 1)
return false;
// 此时背包大小就是元素总和的一半
int V = sum / 2;
// 创建dp表，dp[i][j] 表示在前i个元素中选，总元素和是否等于j
int n = nums.size();
vector<vector<bool>> dp(n + 1, vector<bool>(V + 1, false));
// 初始化第一列为true
for(int i = 0; i <= n; ++i)
dp[i][0] = true;
// 填表
for(int i = 1; i <= n; ++i)
{
for(int j = 1; j <= V; ++j)
{
// 不选i的话，此时判断dp[i - 1][j]是否成立
dp[i][j] = dp[i - 1][j];
// 选i的话，判断一下剩余的空间是否够了 -- 注意原数组的下标映射关系
if(j >= nums[i - 1])
dp[i][j] = dp[i][j] || dp[i - 1][j - nums[i - 1]];
}
}
return dp[n][V];
}
};优化
所有的「背包问题」，都可以进行空间上的优化。
对于 01背包 类型的，我们的优化策略是：
- 删掉第一维
- 修改第二层循环的遍历顺序即可
class Solution {
public:
bool canPartition(vector<int>& nums) {
// 计算出数组中元素总和
int sum = 0;
for(auto e : nums)
sum += e;
// 背包大小不为偶数的话肯定无法分为元素和相等的子集
if(sum % 2 == 1)
return false;
// 此时背包大小就是元素总和的一半
int V = sum / 2;
// 创建dp表
int n = nums.size();
vector<bool> dp(V + 1, false);
// 初始化第一个元素为true
dp[0] = true;
for(int i = 1; i <= n; ++i)
{
for(int j = V; j >= nums[i - 1]; --j) // 修改遍历顺序，并且改变for循环的判断条件，提高效率
{
// 选i的话，判断一下剩余的空间是否够了 -- 注意原数组的下标映射关系
dp[j] = dp[j] || dp[j - nums[i - 1]];
}
}
return dp[V];
}
};