给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
注意
每个数组中的元素不会超过 100
数组的大小不会超过 200
示例 1:
输入: [1, 5, 11, 5]
输出: true
解释: 数组可以分割成 [1, 5, 5] 和 [11].
示例 2:
输入: [1, 2, 3, 5]
输出: false
解释: 数组不能分割成两个元素和相等的子集.
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/partition-equal-subset-sum
这题也是看了评论之后才知道用01背包去做：
先求一遍数组的所有元素之和sum，如果是奇数直接返回false，如果是偶数，我们就考虑使用01背包，对于一个体积为sum/2的背包，我们能否在1~n号物体中选中一部分使得这个背包装满呢？所以问题就转换成了01背包问题，下面给出二维和一维的代码：
二维
class Solution {
public:
bool canPartition(vector<int>& nums) {
int sum = 0;
for(auto x:nums) sum += x;
if(sum &1) return false;
sum /= 2;
int n = nums.size();
vector<vector<bool>> dp(n+1,vector<bool>(sum+1,false));
//dp[i][j] 表示在前i个物品中选，是否可以装满体积为j的背包
for(int i = 1; i<=n; i++)
dp[i][0] = true; //前 i 个物品中选装满体积为0的背包，一定为true
for(int i = 1; i<=n ;i++)
for(int j = nums[i-1]; j<=sum; j++){
dp[i][j] = dp[i-1][j] | dp[i-1][j-nums[i-1]];
}
return dp[n][sum];
}
};
一维
class Solution {
public:
bool canPartition(vector<int>& nums) {
int sum = 0;
for(auto x:nums) sum += x;
if(sum &1) return false;
sum /= 2;
int n = nums.size();
vector<bool> dp(sum+1,false);
//dp[i][j] 表示在前i个物品中选，是否可以装满体积为j的背包
dp[0] = true;
for(int i = 1; i<=n ;i++)
for(int j = sum; j>=nums[i-1]; j--){ //注意遍历方向，
dp[j] = dp[j] |dp[j-nums[i-1]];
}
return dp[sum];
}
};
