416. 分割等和子集*

[MyLinChi]

问题

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

注意:

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

输入: [1, 5, 11, 5]

输出: true

解释: 数组可以分割成 [1, 5, 5] 和 [11].
 

示例 2:

输入: [1, 2, 3, 5]

输出: false

解释: 数组不能分割成两个元素和相等的子集.

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/partition-equal-subset-sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

求解

法一：
暴力回溯（超时）

class Solution {
private:
    int sum=0;
    int len;
    vector<int> nums;
    bool helper(int n,int cur){
        if(cur*2==sum)return true;
        if(n>=len || cur*2>sum)return false;
        return helper(n+1,cur) || helper(n+1,cur+nums[n]);
    }
public:
    bool canPartition(vector<int>& nums) {
        this->nums = nums;
        len = nums.size();
        for(int i=0;i<nums.size();sum +=nums[i++]);
        if(sum &1)return false;
        return helper(0,0);
    }
};

法二：
01背包问题，只是dp(i)(j)表示0~i的物品可以选出一部分刚好装进容量为j的背包。

class Solution {
private:
    vector<vector<int>> dp;
public:
    bool canPartition(vector<int>& nums) {
        int len = nums.size();
        int sum = 0;
        for(int i=0;i<len;sum += nums[i++]);
        if(sum & 1)return false;
        int target = sum/2;
        dp = vector<vector<int>>(len,vector<int>(target+1)  );
        for(int i=0;i<len;++i){
            for(int j=0;j<=target;++j){
                if(i==0){
                    dp[i][j] = j==0 || nums[i]==j;
                }else{
                    dp[i][j] = j==0 || dp[i-1][j] || (j>=nums[i] && dp[i-1][j-nums[i]]);
                }
            }
        }
        return dp[len-1][target];
    }
};

ps：因为工作需要，以后的题解用java写了~

class Solution {
    public boolean canPartition(int[] nums) {
        int len = nums.length;
        int sum = 0;
        for(int n : nums){
            sum += n;
        }
        if((sum&1)==1)return false;
        int target = sum/2;
        boolean[][] dp = new boolean[len][target+1];
        for(int i=0;i<len;++i){
            for(int j=0;j<=target;++j){
                if(i==0){
                    dp[i][j] = j==0 || nums[i]==j;
                }else{
                    dp[i][j] = j==0 || dp[i-1][j] ||(j>=nums[i] && dp[i-1][j-nums[i]]);
                }
            }
        }
        return dp[len-1][target];
    }
}