416. Partition Equal Subset Sum

solution
O(n)
bitset的第i位表示数i能不能通过若干个数组成，通过左移+或可以求出所有可能的和，左移相当于在利用之前所有数得到的所有可能的和的基础上再加上当前这个数，为了不丢失之前的结果还需要或上之前的所有可能的和

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int sum = accumulate(nums.begin(), nums.end(), 0);
        if (sum & 1) return false;
        sum >>= 1;
        bitset<10001> sums(1); // 这里10001够了，因为累加和的一半不会超过10001
        for (int num : nums) {
            sums |= (sums << num);
        }
        return sums[sum];
    }
};

knapsack O(n * sum/2)

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int s = accumulate(begin(nums), end(nums), 0);
        if (s & 1) return false;
        s >>= 1;
        vector<int> f(s + 1);
        f[0] = true;
        for (int x : nums) {
            for (int t = s; t >= x; --t) {
                f[t] = f[t] || f[t - x];
            }
        }
        return f[s];
    }
};