# ISourceCode

Make the frequent cases fast and the rare case correct

## Balanced Partition Problem – Finding the minimized sum between two partitions of a set of positive integers

In Balanced Partition problem,you have a set of n integers each in the range 0 … K. Partition these integers into two subsets such that you minimize |S1 – S2|, where S1 and S2 denote the sums of the elements in each of the two subsets.

A dynamic programming solution to this problem is provided in this video tutorial by Brian C. Dean. It is problem number 7.

The Balanced Partition problem is a variation of the Partitioning problem Which is NP complete. In partitioning problem the objective is to decide whether a given multiset of integers can be partitioned into two “halves” that have the same sum.

There are many ways to solve this problem.

One approach was the way of doing a differencing heuristic similar to what Kamarkar-karp did to solve the partition problem. The Analysis of Kamarkar-Karp can be found at the link.The differencing algorithm at each step removes two numbers from the set and replaces them by their difference.

To get a detail understanding of this problem and why the Kamarkar-Karp approach is not suitable for all cases is described here by American Scientist article by Brian Hayes

Stephan Mertens in this paper describes a optimized algorithm that combines the balanced largest differencing method (BLDM) and Korf’s complete Karmarkar-Karp algorithm.

Algorithm:
Firstly this algorithm can be viewed as knapsack problem where individual array elements are the weights and half the sum as total weight of the knapsack.

1.take a solution array as boolean array sol[] of size sum/2+1

2. For each array element,traverse the array and set sol [j] to be true if sol [j – value of array] is true

3.Let halfsumcloser be the closest reachable number to half the sum and partition are sum-halfsumcloser and halfsumcloser.

4.start from halfsum and decrease halfsumcloser once everytime until you find that sol[halfsumcloser] is true

```import java.io.*;
import java.util.*;

public class balpart
{
public static void main (String [] args) throws IOException
{

int sum = 0;
System.out.println("Enter the number of array elements");
Scanner input = new Scanner(System.in);
int N = input.nextInt();
int[] array = new int[N];
System.out.println("Enter the Positive elements of the array");
for(int member = 0; member < N ; member++)
{
array[member] = input.nextInt();
sum += array[member];
}

boolean [] sol = new boolean [sum / 2 + 1];

sol [0] = true;//empty array
for (int i : array)
{
for (int j = sum / 2; j >= i; j--)
{
if (sol [j - i])
sol [j] = true;
}
}

int halfsumcloser = sum / 2;
for (; !sol [halfsumcloser]; halfsumcloser--);
System.out.println ("The Minimum sum After partioning the array is :" +((sum - halfsumcloser) - halfsumcloser));

}
}
```

OUTPUT:

labuser@ubuntu:~\$ java balpart
Enter the number of array elements
10
Enter the Positive elements of the array
2 10 3 8 5 7 9 5 3 2
The Minimum sum After partioning the array is :0

labuser@ubuntu:~\$ java balpart
Enter the number of array elements
2
Enter the Positive elements of the array
1
5
The Minimum sum After partioning the array is :4

There are further question that we can pose here.

A). In the easiest hard problem article author states that for input
2 10 3 8 5 7 9 5 3 2

there are 23 ways to divide up the numbers into two groups with exactly equal sums
one such partition is [2 5 3 10 7] [2 5 3 9 8]

So can we integrate into this algorithm a method to find the total different ways to make a balanced partition.

B) Can we find the exact partition elements?

The above algorithm takes lot of time on huge numbers resulting in large sums.So again we end up with a not so good algorithm.

One Related article i have already written is Algorithm to implement “Equal Sum Subsets” – For a sequence of numbers, find a subset[s](same order as original sequence) in which each subset has the same smallest sum

That’s it for now. I hope to present more articles on partition problem and its variants

### 6 responses to “Balanced Partition Problem – Finding the minimized sum between two partitions of a set of positive integers”

1. Hudson March 22, 2011 at 4:12 am

What about “minimize |S2 – 2*S1|” partition problem?

2. James Kevin D. Quimbo April 13, 2012 at 4:00 am

Ah Sir can you pls solve this problem pls!
How much space does 2 HDD partitions need from a 500 gigabyte HDD to create a balance HDD!
Thanks!

3. Caroline July 11, 2012 at 7:54 pm

Que fórmula você usou para saber que existem 23 maneiras de dividir os números em dois grupos??

4. Caroline July 11, 2012 at 7:56 pm

What formula you used to know that there are 23 ways to divide the numbers into two groups?

5. Ayodeji April 22, 2013 at 11:54 am

It could be solve as such too

public class Partition {

static int[] arr = {2, 10, 3, 8, 5, 7, 9, 5, 3, 2};//{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11};
static int[] pat;
static int right;
static int left = 0;
static int sumLeft, sumRight;
static int j, k;

static public void main(String[] args) {
Arrays.sort(arr);

right = arr.length – 1;
pat = new int[arr.length];

if (arr.length % 2 == 0) {
calcEven();
} else {
calcOdd();
}
sumUpPartion();
System.out.println(“Left Partition: ” + sumLeft + “\nRight Partition: ” + sumRight);
System.out.println(“Minimum diff: ” + Math.abs(sumLeft – sumRight));

}

static void calcEven() {
for (int i = 0; i < arr.length; i += 2) {
j = arr[i];
k = arr[i + 1];
sumUpPartion();
if (sumLeft <= sumRight) {
pat[left++] = Math.max(j, k);
pat[right–] = Math.min(j, j);
} else {
pat[left++] = Math.min(j, k);
pat[right–] = Math.max(j, k);
}
}
}

static void calcOdd() {
int temp = arr[0];
arr[0] = arr[arr.length – 1];
arr[arr.length – 1] = temp;
for (int i = 0; i < arr.length – 1; i += 2) {
j = arr[i];
k = arr[i + 1];
sumUpPartion();
if (sumLeft sumRight) {
pat[right–] = arr[arr.length – 1];
} else {
pat[left++] = arr[arr.length – 1];
}

}

static void sumUpPartion() {
sumLeft = 0;
sumRight = 0;
int i, n;

int m = pat.length / 2;
if (arr.length % 2 == 0) {
for (i = 0, n = m; i < m || n < pat.length – 1; i++, n++) {
sumLeft += pat[i];
sumRight += pat[n];
}
} else {
for (i = 0, n = m; i < m || n < pat.length; i++, n++) {
//System.out.println(i + " " + j);
sumLeft += pat[i];
sumRight += pat[n];
}
}
}
}