LeetCode/solutions/416. Partition Equal Subset Sum.md

# [416. Partition Equal Subset Sum](https://leetcode.com/problems/partition-equal-subset-sum/)

# 思路
给定一个数组，问这个数组能不能分成两个非空子集合，使得两个子集合的元素之和相同。两个集合元素和相同，也就是都等于所有元素和的一半。
即题目转换成从数组里面选取若干数字使和为一个定值。另外如果所有元素和为奇数的话直接返回false。

## 思路一
我们可以采用一个bitset来记录所有可能的和。具体步骤是：
开辟一个大小为5001的bisets（因为所有元素和不超过10000）名为bits，最后得到的bits满足`bits[i]=1`则代表nums中某些元素的和为i，最后判断bits[sum/2]是否为1即可。处理方法为：

初始时`bits[0] = 1`，然后从前往后遍历nums数组，对于当前遍历到的数字num，把 bits 向左平移 num 位，然后再或上原来的 bits，这样就代表在原先的基础上又新增了一个和的可能性。
比如对于数组 [1,3]，初始化 bits 为 ...00001，遍历到1，bits 变为...00011，然后遍历到3，bits 变为了 ...11011。最终得到的bit在第1,3,4位上为1，代表了可能的和为1,3,4，这样遍历完整个数组后，去看 bits[sum/2] 是否为1即可。


## 思路二
其实本题也可以看做是一个恰好装满的01背包问题，我在我的博客文章[动态规划之背包问题系列](https://tangshusen.me/2019/11/24/knapsack-problem/)对常见的几类背包问题做了个总结，此题的分析见5.1节，这里只给出代码。


# C++
## 思路一
``` C++
class Solution {
public:
    bool canPartition(vector<int>& nums) {
        bitset<5001>bits(1);
        int sum = accumulate(nums.begin(), nums.end(), 0);
        if(sum & 1) return false; // sum为奇数
        for (int &num : nums) bits |= (bits << num);
        return bits[sum >> 1];
    }
};
```

## 思路二
``` C++
bool canPartition(vector<int>& nums) {
    int sum = 0, n = nums.size();
    for(int &num: nums) sum += num;
    if(sum % 2) return false;
    
    int capacity = sum / 2;
    vector<bool>dp(capacity + 1, false);
    dp[0] = true;
    for(int i = 1; i <= n; i++)
        for(int j = capacity; j >= nums[i-1]; j--)
            dp[j] = dp[j] || dp[j - nums[i-1]];
        
    return dp[capacity];
}
```