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:
Maintain running sums for each set.
Add current largest element into the set with smaller sum and update running sums.
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);
}
}
