這道題是一道變形題，可以變型到背包。

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

注意，這道題不能變形到Presum，因?yàn)镻resum數(shù)組的題目，要求數(shù)組是連續(xù)的(Subarray Sum)。如果不連續(xù)(比如求數(shù)組1,3,5,7中能否挑出幾個(gè)數(shù)，使其和為10)，這就是背包問題。

另外，問能不能fill到時(shí)，用一維數(shù)組，從后往前做，如下：

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];
    }
};

滾動(dòng)數(shù)組解法：

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];
        
    }
};