LeetCode.416分割等和子集

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

注意
每个数组中的元素不会超过 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

这题也是看了评论之后才知道用01背包去做：
先求一遍数组的所有元素之和sum，如果是奇数直接返回false，如果是偶数，我们就考虑使用01背包，对于一个体积为sum/2的背包，我们能否在1~n号物体中选中一部分使得这个背包装满呢？所以问题就转换成了01背包问题，下面给出二维和一维的代码：

二维

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int sum = 0;
        for(auto x:nums) sum += x;
        if(sum &1) return false;
        sum /= 2;

        int n = nums.size();
        vector<vector<bool>> dp(n+1,vector<bool>(sum+1,false));

        //dp[i][j] 表示在前i个物品中选，是否可以装满体积为j的背包
        for(int i = 1; i<=n; i++)
            dp[i][0] = true;  //前 i 个物品中选装满体积为0的背包，一定为true

        for(int i = 1; i<=n ;i++)
            for(int j = nums[i-1]; j<=sum; j++){
                dp[i][j] = dp[i-1][j] | dp[i-1][j-nums[i-1]];
            }
        return dp[n][sum];
    }
};

一维

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int sum = 0;
        for(auto x:nums) sum += x;
        if(sum &1) return false;
        sum /= 2;

        int n = nums.size();
        vector<bool> dp(sum+1,false);

        //dp[i][j] 表示在前i个物品中选，是否可以装满体积为j的背包
        dp[0] = true;

        for(int i = 1; i<=n ;i++)
            for(int j = sum; j>=nums[i-1]; j--){  //注意遍历方向，
                dp[j] = dp[j] |dp[j-nums[i-1]];
            }
        return dp[sum];
    }
};