Partition an array of integers into sub-arrays so that the difference of summaries (of sub-arrays) is minimal

Here is one solution (dynamic programming) for partition an array of integers into two sub-arrays so that the difference of summaries (of sub-arrays) is minimal.

// partition an array of integers into two sub-arrays so that the difference of summaries (of sub-arrays) is minimal
int balancePartitionTwoWays(int arr[], int n, int partition[2]) {

 if (n==2) {
  for (int i=0; i<2; i++) {
   partition[i]=arr[i];
  }
  return abs(partition[0]-partition[1]);
 }


 // loop through the array to find out the sum and maximum
 int sum=0;
 int maximum = -1;
 for(int i=0; i<n; i++){
  sum += arr[i];
  if (arr[i]>maximum) maximum = arr[i];
 }

 // allocate the matrix to remember
 bool memo[sum+maximum+1][2];
 for (int j = 0; j < 2; j++)
  for (int i = 0; i <= sum+maximum; i++)
    memo[i][j] = false;

 memo[0][0] = true;

 // mark memo[i][k] to true if there is a subset
    // of array [0..i-1] with sum equal to i
 for (int j = 0; j < n; j++) {
  for (int i = 0; i <= sum+maximum; i++) {

   if (memo[i][j%2]) {
    memo[i][(j+1)%2] = true;
    memo[i+ arr[j]][(j+1)%2] = true;

   }
  }
 }

 int max_diff = INT_MAX;
 int part[2];

 for (int i = 0; i <= sum+maximum; i++) {
  if (memo[i][n % 2]) {
   part[0]=i;
   part[1]=sum-i;
   int temp = abs(part[0]-part[1]) ;
   if (temp<max_diff) {
    max_diff = temp;
    partition[0] = part[0];
    partition[1] = part[1];
   }
  }
 }

 return max_diff;

}

// partition an array of integers into three sub-arrays so that the difference of summaries (of sub-arrays) is minimal
int balancePartitionThreeWays(int arr[], int n, int partition[3]) {

 if (n==3) {
  for (int i=0; i<3; i++) {
   partition[i]=arr[i];
  }
  return abs(partition[0]-partition[1]) + abs(partition[1]-partition[2]) + + abs(partition[2]-partition[0]);
 }


 // loop through the array to find out the sum and maximum
 int sum=0;
 int maximum = -1;
 for(int i =0; i<n; i++){
  sum += arr[i];
  if (arr[i]>maximum) maximum = arr[i];
 }

 // allocate the matrix to remember
 bool memo[sum+maximum+1][sum+maximum+1][2];
 for (int k = 0; k < 2; k++)
  for (int i = 0; i <= sum+maximum; i++)
   for (int j = 0; j <= sum+maximum; j++)
    memo[i][j][k] = false;

 memo[0][0][0] = true;

 // mark memo[i][j][k] to true if there is a subset
    // of array [0..i-1] with sum equal to i
 for (int k = 0; k < n; k++) {
  for (int i = 0; i <= sum+maximum; i++) {
   for (int j = 0; j <= sum+maximum; j++) {
    if (memo[i][j][k%2]) {
     memo[i][j][(k+1)%2] = true;
     memo[i+ arr[k]][j][(k+1)%2] = true;
     memo[i][j+ arr[k]][(k+1)%2] = true;
    }
   }
  }
 }

 int max_diff = INT_MAX;
 int part[3];

 for (int i = 0; i <= sum+maximum; i++) {
  for (int j = 0; j <= sum+maximum; j++) {

   if (memo[i][j][n % 2]) {
    part[0]=i;
    part[1]=j;
    part[2]=sum-i-j;

    //int temp = abs(part[0]-part[1]) + abs(part[1]-part[2]) + + abs(part[2]-part[0]);
    int temp = 0;
    for (int k=0; k<3; k++) {
     temp += abs(part[k%3]-part[(k+1)%3]);
    }
    if (temp<max_diff) {
     max_diff = temp;
     for (int k=0; k<3; k++) {
      partition[k]=part[k];
     }
    }
   }
  }
 }

 return max_diff;

}

Enjoy the journey.