Make delicious recipes!

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:

Facebook comments:

Site Owner: Sachin Goyal