Equal sum partition (DP-09)

You are given a set of positive integers. You need to find whether or not, the set can be divided into to partitions of equal sum.

Sample Input: { 7, 3, 1, 5, 4, 8 }.
Expected Output: True.
Explanation: One possible solution is that the set can be divided into two subsets { 7, 3, 4} and { 1, 5, 8 } which has equal sum 14. There might exist other solutions as well.

Algorithm:

This problem is a special case of the subset sum problem which is a special case of 0-1 knapsack problem.

1. If the total sum of the array is odd, then the array cannot be divided into two partitions of equal sum.
2. If the total sum is even, then we can apply the same technique as used in subset sum problem with given sum = (total_sum) / 2
3. Please refer to the subset sum problem for further details.

/* Author => Raunak Jain */
#include <bits/stdc++.h>
using namespace std;

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

int main(){
	int sum=0;
	vector<int> nums = { 7, 3, 1, 5, 4, 8 };
	for(auto i:nums){
		sum+=i;
	}
	if(!(sum&1) && helper(nums, sum/2)){
		cout<<"True";
	}else{
		cout<<"False";
	}
	return 0;
}

Also, check out another popular interview question Pots of gold.