可惜一溪风月
莫教踏碎琼瑶
C++，动态规划，01背包。
这道题需要稍微转变点思路，就是01背包了哈哈哈。
首先可以肯定的是，序列总和必须为偶数，因为得由两个和相等的集合相加而成。
然后就变成了，找到若干元素组成的子序列，该子序列的和等于总和的半数。
这不就是01背包吗？？？虽然我忘了01背包怎么写了2333。
定义一个数组：vector<bool> dp(sum + 1);，dp[x]表示x可以由序列中的若干元素相加而得。
01背包：外循环以循环变量it遍历序列中所有元素，内循环从sum开始，逐一递减，判断是否能由it加上dp中更小的元素得到和，也就是dp[j - it] == true ?，还有个优点就是不用担心重复2333。
知道上述思路就很简单了。
class Solution {
public:
bool canPartition(vector<int>& nums) {
int sum = 0;
for (const auto &it : nums) {
sum += it;
}
if (sum % 2 == 1) return false;
sum /= 2;
vector<bool> dp(sum + 1);
dp[0] = true;
for (int &it : nums) {
for (int j = sum; j >= it; j--) {
if (dp[j - it])
dp[j] = true;
}
}
return dp[sum];
}
};
