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:
- Each of the array element will not exceed 100.
- 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];
}
};