原题地址（中等）

又是可恶的动规！！

开始我想用回溯遍历，再加一丢丢减枝，结果还是超出时间限制。

没想到这题是0-1背包的变种。

直接看了官方题解。

代码

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int n = nums.size();
        if(n == 0)  return true;
        int sum = accumulate(nums.begin(), nums.end(), 0);
        if(sum % 2 != 0)    return false;
        int target = sum / 2;
        int maxVal = *( max_element(nums.begin(), nums.end()) );
        if(maxVal > target) return false;
        vector<int> dp(target + 1, 0);
        dp[0] = 1;
        for(int i=0; i < n; i++) {
            int num = nums[i];
            for(int j = target; j >= num; j--) {
                    dp[j] |= dp[j-num];
            }
        }
        return dp[target];
    }
};