## Balanced Partition Problem

Follow the logic of Balanced Partition Problem from here

#include <iostream> #include <vector> #include <algorithm> #include <climits> #include <cmath> using namespace std; int BalancedPartition(vector<int> v) { int n = v.size(); int sum = accumulate(v.begin(),v.end(),0); int max_sum=sum/2,diff=INT_MAX; int *s = new int[sum+1]; s[0] = 1; for(int i=1; i<=sum; i++) s[i] = 0; for(int i=0; i<n; i++) { for(int j = sum; j>=0; j--) { if(s[j]) { s[j+v[i]]+=1; } } } for(int j = sum/2; j>=1; j--) if(s[j]) { return abs(sum-2*j); } } int main() { int value[] = {12,5,7,3}; int n = sizeof(value)/sizeof(value[0]); vector<int> v(value,value+n); cout<<BalancedPartition(v); return 0; }

Advertisements

No comments yet.

Advertisements

## Leave a Reply