Partition Equal Subset Sum -- LeetCode 416

[Question]

Given a non-empty array containing only positive integers, find if the array can be partitioned into two subsets such that the sum of elements in both subsets is equal.

Note:

1. Each of the array element will not exceed 100.
2. The array size will not exceed 200.

Example 1:

Input: [1, 5, 11, 5]

Output: true

Explanation: The array can be partitioned as [1, 5, 5] and [11].

Example 2:

Input: [1, 2, 3, 5]

Output: false

Explanation: The array cannot be partitioned into equal sum subsets.

[Analysis]
This is a simplified Knapsack problem. The typical dynamic programming solution is to define dp[i][j] as if first i elements can get a sum of j, dp[0][0] is apparently true. The question becomes whether dp[n][m] is true, where n is the size of the input array and m is the half of the sum of n numbers. Furthermore,
        dp[i][j] = d[i-1][j]                       // if do not select the i-th element
                       || d[i-1][j- nums[i] ]      // if select the i-th element

Since the iteration of the dp calculation is along the i variable. The 2-dimension dp formula can be implemented by one dimensional array. Therefore, the space complexity is O(M), M is the sum of all numbers; the time complexity is O(NxM).

Interestingly, because of the assumption on array elements -- every element <=100 and the array size is <= 200 , the sum of whole array is less than 20,000.  There is a faster solution using bit manipulation to calculate all subset of the array. The bit manipulation approach can achieve the time complexity O(N) and space complexity O(M).

Derived from the bit manipulation, there is brute force approach to calculate all subset's sum using set but the time complexity will be O(2^N), much slower.

[Solution]
//-- Dynamic Programming O(NxM)  --
class Solution {
public:
    bool canPartition(vector<int>& nums) {
        //dp[i, j] -- first i elements can make a sum of j
        //dp[0,0]= true;
        //dp[i, j] = dp[i-1, j] || dp[i-1, j-A[i-1] ];
        int sum = accumulate(nums.begin(), nums.end(), 0);
        if (sum%2) return false;
        
        vector<bool> dp(sum/2+1, false);
        dp[0] = true;
        
        for (int i=0; i<nums.size(); i++)
            for (int j=dp.size()-1; j>0; j--)  // -- must be in reversed order. 
                dp[j]= dp[j] || j>=nums[i] && dp[ j-nums[i] ];
        return dp.back();
    }
};

//-- Back Tracking --
class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int sum = 0;
        for(int i =0;i<nums.size();i++){
            sum+= nums[i];
        }
        if(sum%2) return false;
        sum /= 2;
        sort(nums.rbegin(),nums.rend());
        return helper(nums, sum, 0);
    }
    bool helper(vector<int>& nums, int sum, int index){
        if(sum == nums[index]) return true;
        if(sum < nums[index]) return false;
        return helper(nums,sum-nums[index],index+1) || helper(nums,sum,index+1);
    }
};

//-- Bit Manipulation O(N) --
class Solution {
public:
    bool canPartition(vector<int>& nums) {
        bitset<10001> bits(1);   // -- assume the max sum is 20,000.
        int sum = accumulate(nums.begin(), nums.end(), 0);
        for (auto n : nums) bits |= bits << n; 
        return !(sum & 1) && bits[sum >> 1];
    }
};

//-- Brute Force --
class Solution {
public:
    bool canPartition(vector<int>& nums) {
        unordered_set<int> sub;
        sub.insert(0);
     
        int sum  = accumulate(nums.begin(), nums.end(), 0);
        if ((sum %2) == 1) return false;
     
        for (auto n: nums) {
            unordered_set<int> temp;
            for (auto x:sub) {
                temp.insert(x+n);
            }
            sub.insert(temp.begin(), temp.end());
        }
     
        return sub.count(sum/2);
    }
};