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

注意:

1. 每个数组中的元素不会超过 100
2. 数组的大小不会超过 200

示例 1:

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

输出: true

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

示例 2:

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

输出: false

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

Solution

参考：《算法小抄》2.16 、liuyubobobo

• 将问题转化为：给一个可装载重量为 sum/2 的背包和 N 个物品，每个物品的重量为 nums[i] 。是否存在一种装法，能够恰好将背包装满？

# @lc code=start
class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        sum_n = 0
        n = len(nums)
        for i in nums:
            sum_n+=i
        if sum_n % 2 != 0: return False
        sum_n = int(sum_n / 2)
        dp = [[False for _ in range(sum_n+2)] for _ in range(n+2)]
        
        for i in range(n+1):
            dp[i][0] = True
        for i in range(1, n+1):
            for j in range(1, sum_n+1):
                if j-nums[i-1]<0:
                    dp[i][j]=dp[i-1][j]
                else:
                    dp[i][j]=dp[i-1][j] or dp[i-1][j-nums[i-1]]
        return dp[n][sum_n]
# @lc code=end

cpp

• 记忆优化搜索，自顶向下

class Solution {
private:
    // memo[i][c] 表示使用索引为[0...i]的这些元素,是否可以完全填充一个容量为c的背包
    // -1 表示为未计算; 0 表示不可以填充; 1 表示可以填充
    vector<vector<int>> memo;

    bool go(const vector<int>& nums, int index, int sum){
        if(sum==0)
            return true;
        if(sum<0 || index <0)
            return false;

        if(memo[index][sum] != -1)
            return memo[index][sum]==1;

        memo[index][sum] = (go(nums, index-1, sum) ||
                            go(nums, index-1, sum-nums[index])) ? 1:0;
        return memo[index][sum]==1;
    }

public:
    bool canPartition(vector<int>& nums) {
        int n = nums.size();
        if(n<2) return false;

        int sum = 0;
        for(int num : nums)
            sum += num;
        if(sum%2==1) return false;

        memo = vector<vector<int>>(n, vector<int>(sum/2+1, -1));
        return go(nums, n-1, sum/2);
    }
};

• dp 数组，状态压缩

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int n = nums.size();
        if(n<2) return false;

        int sum = 0;
        for(int num : nums)
            sum += num;
        if(sum%2==1) return false;

        int C = sum/2;
        vector<bool> dp(C, false);
        for(int i=0; i<=C; ++i)
            dp[i] = (nums[0]==i);

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