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.
- If the total sum of the array is odd, then the array cannot be divided into two partitions of equal sum.
- 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
- 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.
2 comments