Given non-empty array nums 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.
Partition Equal Subset Sum - LeetCode
Example 1:
Input: nums = [1,5,11,5]
Output: true
Explanation: The array can be partitioned as [1, 5, 5] and [11].
This problem is similar to subset sum problem only difference is that we have to return false when the total sum of all the elements of the given array is odd. In case of an even sum array we have find a subset whose sum is half of the total sum.
bool canPartition(vector<int>& nums) {
int sum = 0;
for(int ele:nums)
sum+=ele;
if(sum%2)
return false;
int halfsum = sum/2;
int n = nums.size();
bool dp[n+1][halfsum+1];
for(int i=0;i<=n;i++)
{
for(int j=0;j<=halfsum;j++)
{
if(i==0&&j!=0)
dp[i][j] = false;
else if(j==0)
dp[i][j] = true;
else if(j>=nums[i-1])
dp[i][j] = dp[i-1][j-nums[i-1]] || dp[i-1][j];
else
dp[i][j] = dp[i-1][j];
}
}
return dp[n][halfsum];
}