题目描述

给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

注意:

每个数组中的元素不会超过 100
数组的大小不会超过 200

示例 1:
输入: [1, 5, 11, 5]
输出: true
解释: 数组可以分割成 [1, 5, 5] 和 [11].

C++ 代码

#include<numeric>

class Solution {
public:
    bool canPartition(vector<int>& nums) {
//两边尽可能等分，
//等价于nums[i]作为包重量和价值，包限量为sum/2
//dp[i]的意思表示容量为i的背包的价值累加能否获得num/2
//dp初始化为
    int n = nums.size();
    // int sum = accumulate(nums.begin(),nums.end(),0);
    int sum = 0;
    for(auto num:nums)sum+=num;
    if(sum&1)return false;
    vector<bool> dp(sum/2+1,false);
    for(int i = 0;i<=sum/2;i++){
        dp[i] = (nums[0]==i);
    }
    for(int i = 1;i<n;i++){
        for(int j = sum/2 ;j>=nums[i];j--){
            dp[j] = dp[j]||(dp[j-nums[i]]);
        }
    }
    return dp[sum/2];
}

};