Data Structuresand Algorithms Good OldJava AdvancedInterview Topics Cloud andDatabases Web Designand Development Must-knowTools Good ToKnow

## Divide an array of integers into nearly equal sums

Problem: Given an array of unsorted integers, divide it into two sets, each having (arr.length/2) elements such that the sum of each set is as close to each other as possible.

Solution: This can be done by first sorting the array (O nlogn) and then applying the following algorithm:
1. Maintain running sums for each set.
2. Add current largest element into the set with smaller sum and update running sums.
3. If any set reaches capacity n/2, then simply put remaining elements into the other set.

Code:
```
import java.util.Arrays;

public class TwoSetsWithEqualSums
{

public static void main (String args[])
{
int arr[] = {4, 5, 8, 1, 3, 9, 7, 11, 100, 74, 83, 65};
int set1[] = new int[(1+arr.length)/2];
int set2[] = new int[(1+arr.length)/2];

divideInEqualSums (arr, set1, set2);
}

private static void divideInEqualSums(int[] arr, int[] set1, int[] set2)
{
int setSize = set1.length;
Arrays.sort(arr);

int pos1=0;
int pos2=0;

int i=arr.length-1;

int sum1 = 0;
int sum2 = 0;
while (pos1 < setSize && pos2 < setSize)
{
if (sum1 < sum2)
{
set1[pos1] = arr[i];
pos1++;
sum1 += arr[i];
}
else
{
set2[pos2] = arr[i];
pos2++;
sum2 += arr[i];
}
i--;
}

while (i>=0)
{
if (pos1 < setSize)
set1[pos1++] = arr[i];
else
set2[pos2++] = arr[i];
i--;
}

printArrayWithSum(arr);
printArrayWithSum(set1);
printArrayWithSum(set2);
}

static void printArrayWithSum (int arr[])
{
int sum1 = 0;
for (int i=0; i<arr.length; i++)
{
sum1 += arr[i];
System.out.print(arr[i]+",");
}
System.out.println(" = " + sum1);
}
}

```

Sample Execution:
```1,3,4,5,7,8,9,11,65,74,83,100, = 370
83,74,11,8,5,3, = 184
100,65,9,7,4,1, = 186
```

Like us on Facebook to remain in touch
with the latest in technology and tutorials!

Got a thought to share or found a
bug in the code?
We'd love to hear from you:

 Name: Email: (Your email is not shared with anybody) Comment: