Leetcode 416: Partition Equal Subset Sum

https://leetcode.com/problems/partition-equal-subset-sum/description/

Notes:

This question is a typical 01 knapsack problem. Please refer this post for knapsack problems.

See the code below:

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

The above time complexity is O(N*V), where N is the number of elements and V is the volume or sum.

There is a very inspiring method to record all the possible sum with O(V) time complexity. Using bitset!!!

Based on the definition, bs[idx] can only be two kinds of value: 0 or 1, or false or true. When bs[idx] = =1, means there is a sum == idx.

See the code below:

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        bitset<50000> bs(1);//initial size and set bs[0] = 1;
        int sum = 0;
        for(auto &a : nums) {
            bs |= bs << a;//all the previous sum + a
            sum += a;
        }
        return !(sum&1) && bs[sum>>1];
    }
};

There is a follow up to this question, please refer to this post.