# Balanced partition problem

Balanced partition problem a problem of dividing any given things into two equal valued parts. Value can be anything, it can be just numbers or some abstract notion attached to items in array. Let’s understand our problem for today : **Divide an array of integers, into two balanced partitions**. By balanced partitioning of array, we mean to divide array into two subsets (subsets are different from subarrays, subset can contain elements of array which are not contiguous where as subarray can contain elements which are contiguous) such that difference of sum of two sub sets is minimum, Best case will be when sum of two subsets are equal. This is a NP hard problem if there is no limit on the total sum of array but can be solved in O(n * N) if total sum has limit of N.

For example, in following array, difference between two subsets will be 1.

int c[] = {1,7,4,11}; {1,11} and {7,4}, so most balanced partition of given array c are {1,11} and {7,4}.

Some times problem is asked in a different way; for example there are 22 players and each player has a value associated with him which it brings to the team. Divide them into two teams of eleven each, so that difference between overall values of teams is minimum.

## Balanced partition problem : Algorithm analysis

Brute force method to divide array into two balanced partition, so that difference between two parts is minimum is to list all the subsets of given array and select two among them which have their difference as minimum. It has exponential complexity as number of subsets for an array of size n are n! and cannot be implemented for moderately big sized arrays.

Before going to the generic solution to this problem, let me tweak this problem a bit. What if we need to find out if there are two subsets of integers in array such that difference between sum of these two is zero. Essentially this is a special case of above given problem.

How should we go about solving the specific case of original problem? If difference between two sets is zero that means sum of both sets should be exactly equal to half of sum of all elements in array.Why? Because if any one subset is greater than or less than half of sum of all elements, then difference cannot be zero.

Now we get a specific version of problem which reduces find if there is subset of integers which add up to half the sum of all elements in array? This is subset sum problem which we have already solved here Subset sum problem

There is another simpler version of finding if there are some sets of array which add up to half of the sum of array. it goes like : take a table T of size N +1 where N is total sum of all elements of array. In this array, T[x] is true only if there are some elements in array which add up to x. Once , we fill all the entries, just check if T[N/2] is true or not.

Now how to build this array? Start with T[0] which will be true as we can always have sum equal to zero with empty set. Now set T[C[i]] will be set to true as we can have sum C[i] by taking element C[i]. C is given array here.

Now, when we have let’s T[j] set to true, that means we have some subset which adds up to j. In that case while processing C[i] we should also make T[j+ C[i]] as true because by add C[i] in previous subset, we can get new subset with sum j+C[i]

Above code can be optimized where we don’t calculate T[N-x] entries as if T[x] is true, other remaining sub set will eventually add up to N-x where N is total sum.

int T[10240]; int partition(int C[], int size){ //compute the total sum int N= 0; for(int i= 0;i<n;i++) N+=C[i]; //initialize the table T[0]=true; for(int i=1;i<=N;i++)T[i]= false; //process the numbers one by one for (int i=0; i<n; i++){ for(int j=N-C[i]; j>=0; j--){ if(T[j]) T[j+C[i]]= true; } } return T[N/2]; }

Problem becomes a bit tricky when we don’t to just find equal sum two subset but two subsets with minimum difference sum. Extra information which says what are the possible sums which can be generated using subsets of integers of given array in above step can be helpful.

Sum of all numbers in integers is given by N. Let’s half it and find a subset which has sum as close as possible to this half. That will give us other subset which is least greater than half of sum of all elements of array and that will be minimum difference possible between two subsets. 🙂 Our expression would be

## Balanced partition problem : Implementation

#include <stdio.h> #include <stdlib.h> int balancePartition(int set[], int n) { /*The value of subset[i][j] will be true if there is a subset of set[0..j-1] with sum equal to i */ int i,j; int sum =0; for(i =0; i<=n; i++){ sum += set[i]; } int subset[sum+1][n+1]; // If sum is 0, then answer is true for (i = 0; i <= n; i++) subset[0][i] = true; // If sum is not 0 and set is empty, then answer is false for (i = 1; i <= sum; i++) subset[i][0] = false; // Fill the subset table in botton up manner for (i = 1; i <= sum; i++) { for ( j = 1; j <= n ; j++) { subset[i][j] = subset[i][j-1]; if (i >= set[j-1]){ subset[i][j] = subset[i][j] ||subset[i-set[j-1]][j-1]; } } } int min =INT_MAX; for(i=1; i<=sum; i++){ for(j=1; j<=n; j++){ /* If there is s subset with sum i, then check if the difference between overall sum and twice this sum is least or not. If yes update the min */ if(subset[i][j] == true){ if(abs(sum - 2*i) < min){ min = abs(sum - 2 *i); } } } } printf("\n Difference between two sub sets will be : %d\n", min); } int main(){ int a[] = {1,7,4,11}; int n = sizeof(a)/sizeof(a[0]); balancePartition(a,n-1); return 0; }

Complexity to split an array into two **balanced partitions** is O(nN) with space complexity of O(nN), where N is total sum of array.

Please share if there is something wrong or missing. If you are interested in contributing to website, please contact us and earn too.