Partition Equal Subset Sum (Leet

这道题是一道变形题，可以变型到背包。

建立背包，表示是否可以拿到总和的一半。

注意，这道题不能变形到Presum，因为Presum数组的题目，要求数组是连续的(Subarray Sum)。如果不连续(比如求数组1,3,5,7中能否挑出几个数，使其和为10)，这就是背包问题。

另外，问能不能fill到时，用一维数组，从后往前做，如下：

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        if(nums.empty()) return false;
        int sum = 0;
        for(auto it : nums){
            sum += it;
        }
        
        if(sum % 2 != 0) return false;
        int val = sum / 2, size = nums.size();
        
        vector<int> dp(val+1, 0);
        dp[0] = true;
        
        for(int i=1; i<=nums.size(); i++){
            for(int j=val; j>=nums[i-1]; j--){
                dp[j] = dp[j] || dp[j-nums[i-1]];
            }
        }
        return dp[val];
    }
};

滚动数组解法：

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        if(nums.empty()) return true;
        int sum = accumulate(begin(nums), end(nums), 0, plus<int>());
        if(sum % 2 != 0) return false;

        int size = nums.size();
        int val = sum/2;
        vector<vector<int>> dp(2, vector<int>(val+1, 0));
        for(int i=1; i<=size; i++){
            for(int j=1; j<=val; j++){
                if(j < nums[i-1]) dp[i%2][j] = dp[(i-1)%2][j];
                else{
                    dp[i%2][j] = max(dp[(i-1)%2][j], dp[(i-1)%2][j-nums[i-1]] + nums[i-1]);
                }
            }
        }
        return dp[size%2][val] == sum - dp[size%2][val];
        
    }
};