class Solution {
public:
bool canPartition(std::vector<int>& nums) {
int sum = accumulate(nums.begin(), nums.end(), 0);
if (sum%2) return false;
// dp[j] 背包和为j时最大价值为dp[j]
std::vector<int> dp(sum/2+1);
for (int i=0;i<nums.size();i++)
for(int j=sum/2;j>=nums[i];j--)
// 此处重量和价值一样 都是nums[i]
dp[j] = std::max(dp[j-nums[i]]+nums[i], dp[j]);
// 集合中的元素正好可以凑成总和target
if (dp[sum/2]==sum/2) return true;
return false;
}
};