# Partition Equal Subset Sum

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.


Solution 1:

DP: knapsack

class Solution {
public:
bool canPartition(vector<int>& nums) {
int sum = 0;
for(int i : nums) sum+=i;
if(sum %2) return false;
sum/=2;

vector<vector<int>> dp(nums.size()+1, vector<int>(sum+1, 0));
dp[0][0] = 1;
for(int i= 1; i<=nums.size();i++){
for(int j=0; j<=sum; j++){
dp[i][j] |= dp[i-1][j];
if(j>=nums[i-1])dp[i][j] |= dp[i-1][j-nums[i-1]];
}
}
return dp[nums.size()][sum];
}
};


Solution 2:

Bitmap, similar idea with dp but with better data structure

class Solution {
public:
bool canPartition(vector<int>& nums) {
int sum = 0;
bitset<20001> bit(1);
for(int i : nums){
sum += i;
bit |= bit<<i;
}
return !(sum&1) && bit[sum>>1];
}
};