Balanced partition problem: Dynamic programming

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.

  • Sanchita Tiwari

    can u please explain the step why abs(sum – 2*i)? particularly why are you using 2*i why not only i ?

    • http://algorithmsandme.in/ Jitendra Sangar

      If we have a subset with sum i, we want to make sure that the other part that is sum -i should be minimum. That can be minimum only if i is minimally deviate from sum/2. To avoid sum/2, I have multiplied i with 2 and subtracted it from the whole sum. Hope it clarifies things.

  • Tessa

    what if you want this to actually print the subsets?

  • Mr. Lazy

    Exponential Implementation to print the subsets .. http://ideone.com/g9HvtO

  • Shivam

    Will this work even if array is of type float?

    • http://algorithmsandme.com/ Jitendra Sangar

      Not sure if it will work for float type! IMO it should.

  • Nitin Gera

    How do u ensure the subset size is n/2. For example if our array is
    8 100 54 29 1 2
    Won’t your subsets be 8 54 29 1 2 and 100 rather than
    100 1 2 and 8 54 29
    according to ypur explanation

    • Guohui Wang

      Exactly, the solution cannot guarantee to generate two equal size subsets.

      • http://algorithmsandme.com/ Jitendra Sangar

        Yes, solution does not guarantee that two halves will be equal in size (which is not ask in problem statement anyways). It only guarantees that difference between two halves will be minimum.

        • Guohui Wang

          From you post: “Balance partition as term states is a process of dividing any given thing into two equal parts.”

          And the example given is soccer team, 22 people divided into 2 teams, 11 each.

          These all indicate that the two result halves should be equal in size.

          • http://algorithmsandme.com/ Jitendra Sangar

            Sorry, I will clarify the problem statement again. It was not the intention at all. Thanks for pointing out.