Leetcode-分割等和子集（中等）

题目描述

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

输入：nums = [1,5,11,5]
输出：true
解释：数组可以分割成 [1, 5, 5] 和 [11] 。

首先nums元素和sum必须是偶数，否则false
转换成01背包问题，放入nums中的一些数字，能够得到和为sum/2
所以对每个元素，可以放可以不放
dp[i][j]表示截止到第i个元素，能够得到和为j的情况。
dp[i][j]=dp[i-1][j]+dp[i-1][j-nums[i]]
前者表示在i号元素之前就可以得到，后者在j>=nums[i]时，表示放入第i号元素，在此之前需要能够凑到和为j-nums[i]
最后输出dp[nums.size()-1][sum/2]

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int sum=0;
        for(auto i:nums) sum+=i;
        if(sum&1) return false;
        vector<vector<bool>> dp(nums.size(),vector<bool>(sum/2+1,false));
        //行号是数组元素，从dp[0]-dp[nums.size()]
        //列号是可以求得的和，从dp[][0]-dp[][sum/2] 
        int target=sum/2;
        if(nums[0]==target) return true;
        if(nums[0]<target)
            dp[0][nums[0]]=true;
        for(int i=1;i<nums.size();i++){
            for(int j=0;j<target+1;j++){
                dp[i][j]=dp[i-1][j];
                if(nums[i]==target) return true;
                if(nums[i]<=j) 
                    dp[i][j]=dp[i-1][j]||dp[i-1][j-nums[i]];
                    //一种是不选nums[i],但是前面已经能够得到和为j
                    //另一种是选nums[i]，且前面能得到和为j-nums[i]
            }
        }
        return dp[nums.size()-1][target];
    }
};