How to divide a set of numbers into two sets such that the difference of their sum is minimum

Question

How to write a Java Program to divide a set of numbers into two sets such that the difference of the sum of their individual numbers, is minimum.

For example, I have an array containing integers- [5,4,8,2]. I can divide it into two arrays- [8,2] and [5,4]. Assuming that the given set of numbers, can have a unique solution like in above example, how to write a Java program to achieve the solution. It would be fine even if I am able to find out that minimum possible difference. Let's say my method receives an array as parameter. That method has to first divide the array received into two arrays, and then add the integers contained in them. Thereafter, it has to return the difference between them, such that the difference is minimum possible.

P.S.- I have had a look around here, but couldn't find any specific solution to this. Most probable solution seemed to be given here- divide an array into two sets with minimal difference . But I couldn't gather from that thread how can I write a Java program to get a definite solution to the problem.

EDIT:

After looking at the comment of @Alexandru Severin, I tried a java program. It works for one set of numbers [1,3,5,9], but doesn't work for another set [4,3,5,9, 11]. Below is the program. Please suggest changes:-

 import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class FindMinimumDifference {
public static void main(String[] args) {
    int[] arr= new int[]{4,3,5,9, 11};  
    FindMinimumDifference obj= new FindMinimumDifference();
    obj.returnMinDiff(arr);
}

private int  returnMinDiff(int[] array){


    int diff=-1;
    Arrays.sort(array);
    List<Integer> list1= new ArrayList<>();
    List<Integer> list2= new ArrayList<>();
    int sumOfList1=0;
    int sumOfList2=0;
    for(int a:array){
        for(Integer i:list1){
            sumOfList1+=i;
        }
        for(Integer i:list2){
            sumOfList2+=i;
        }
        if(sumOfList1<=sumOfList2){
        list1.add(a);
        }else{
            list2.add(a);
        }
    }

    List<Integer> list3=new ArrayList<>(list1);   
    List<Integer> list4= new ArrayList<>(list2);   
    Map<Integer, List<Integer>> mapOfProbables= new HashMap<Integer, List<Integer>>();
    int probableValueCount=0;
    for(int i=0; i<list1.size();i++){  
        for(int j=0; j<list2.size();j++){
            if(abs(list1.get(i)-list2.get(j))<
abs(getSumOfEntries(list1)-getSumOfEntries(list2))){
                List<Integer> list= new ArrayList<>();
                list.add(list1.get(i));
                list.add(list2.get(j));    
                mapOfProbables.put(probableValueCount++, list);
            }
        }
    }
    int minimumDiff=abs(getSumOfEntries(list1)-getSumOfEntries(list2));
    List resultList= new ArrayList<>();
    for(List probableList:mapOfProbables.values()){  
        list3.remove(probableList.get(0));
        list4.remove(probableList.get(1));
        list3.add((Integer)probableList.get(1));
        list4.add((Integer)probableList.get(0));
        if(minimumDiff>abs(getSumOfEntries(list3)-getSumOfEntries(list4))){ 
// valid exchange 
                minimumDiff=abs(getSumOfEntries(list3)-getSumOfEntries(list4));
                resultList=probableList;
        }

    }

    System.out.println(minimumDiff);

    if(resultList.size()>0){
        list1.remove(resultList.get(0));
        list2.remove(resultList.get(1));
        list1.add((Integer)resultList.get(1));
        list2.add((Integer)resultList.get(0));
    }

    System.out.println(list1+""+list2);  // the two resulting set of 
// numbers with modified data giving expected result

    return minimumDiff;
}

private static int getSumOfEntries(List<Integer> list){
    int sum=0;
    for(Integer i:list){
        sum+=i;
    }
    return sum;
}
private static int abs(int i){
    if(i<=0) 
        i=-i;
    return i;
}
}

Answer 1

I seem to have got the perfect solution for this. Below Java program works perfectly. Only assumption is that, the given problem has unique solution (just one solution). This assumption implies- only non-zero number. I am putting the program below. I request everyone to tell if the program could fail for certain scenario, or if it could be improved/optimized in some way. Credits to Mr Alexandru Severin's algorithm posted as one of the answers in this thread.

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class FindMinimumDifference {

static List<Integer> list1= new ArrayList<>();
static List<Integer> list2= new ArrayList<>();

public static void main(String[] args) {
    int[] arr= new int[]{3,-2,9,7};  
    // tested for these sample data:- [1,5,9,3] ; [4,3,5,9,11] ; 
//[7,5,11,2,13,15,14] ; [3,2,1,7,9,11,13] ; 
    //[3,1,0,5,6,9] ; [6,8,10,2,4,0] ; [3,1,5,7,0] ; [4,-1,5,-3,7] ; [3,-2,9,7]

    System.out.println("the minimum possible difference is: "+returnMinDiff(arr));
    System.out.println("the two resulting set of nos. are: "+list1+" and "+list2);
}

private static int  returnMinDiff(int[] array){
    int diff=-1;
    Arrays.sort(array);

    for(int a:array){
        int sumOfList1=0;
        int sumOfList2=0;

        for(Integer i:list1){
            sumOfList1+=i;
        }
        for(Integer i:list2){
            sumOfList2+=i;
        }
        if(sumOfList1<=sumOfList2){
        list1.add(a);
        }else{
            list2.add(a);
        }
    }

    List<Integer> list3=new ArrayList<>(list1);   
    List<Integer> list4= new ArrayList<>(list2); 
    if(list3.size()!=list4.size()){     // both list should contain equal no. of entries. 
        //If not, add 0 to the list having lesser no. of entries
        if(list3.size()<list4.size()){
            list3.add(0);
        }else{
            list4.add(0);
        }
    }
    Map<Integer, List<Integer>> mapOfProbables= new HashMap<Integer, List<Integer>>();
    int probableValueCount=0;
    for(int i=0; i<list3.size();i++){  
        for(int j=0; j<list4.size();j++){
            if(abs(list3.get(i)-list4.get(j))
   <abs(getSumOfEntries(list3)-getSumOfEntries(list4))){
                List<Integer> list= new ArrayList<>();
                list.add(list3.get(i));
                list.add(list4.get(j));    
                mapOfProbables.put(probableValueCount++, list);
            }
        }
    }
    int minimumDiff=abs(getSumOfEntries(list1)-getSumOfEntries(list2));
    List resultList= new ArrayList<>();
    for(List probableList:mapOfProbables.values()){ 
        list3=new ArrayList<>(list1);   
        list4= new ArrayList<>(list2);
        list3.remove(probableList.get(0));
        list4.remove(probableList.get(1));
        list3.add((Integer)probableList.get(1));
        list4.add((Integer)probableList.get(0));
        if(minimumDiff>abs(getSumOfEntries(list3)-getSumOfEntries(list4))){ // valid exchange 
                minimumDiff=abs(getSumOfEntries(list3)-getSumOfEntries(list4));
                resultList=probableList;
        }

    }

    if(resultList.size()>0){   // forming the two set of nos. whose difference of sum comes out to be minimum
        list1.remove(resultList.get(0));
        list2.remove(resultList.get(1));
        if(!resultList.get(1).equals(0) )   // (resultList.get(1).equals(0) && !list1.contains(0))
            list1.add((Integer)resultList.get(1));
        if(!resultList.get(0).equals(0) || (resultList.get(0).equals(0) && list2.contains(0)))
            list2.add((Integer)resultList.get(0));
    }

    return minimumDiff; // returning the minimum possible difference
}

private static int getSumOfEntries(List<Integer> list){
    int sum=0;
    for(Integer i:list){
        sum+=i;
    }
    return sum;
}
private static int abs(int i){
    if(i<=0) 
        i=-i;
    return i;
}
}

Answer 2

It seems that you are more interested in the algorithm than the code. So, here is my psuedocode:-

int A[];//This contains your elements in sorted (descending) order
int a1[],a2[];//The two sub-arrays
int sum1=0,sum2=0;//These store the sum of the elements of the 2 subarrays respectively
for(i=0;i<A.length;i++)
{
//Calculate the absolute difference of the sums for each element and then add accordingly and thereafter update the sum
    if(abs(sum1+A[i]-sum2)<=abs(sum2+A[i]-sum1))
           {a1.add(A[i]);
            sum1+=A[i];}
    else
           {a2.add(A[i]);
            sum2+=A[i];}
}

This will work for all integers, positive or negative.

Answer 3

First of all, sorting the array then putting first member in group and second in another wound never work, and here is why:

Given the input[1,2,3,100]. The result would be: [1,3] and [2,100], clearly wrong. The correct answer should be: [1,2,3] and [100]

You can find many optimization algorithms on google for this problem, but since I assume you're a beginner, I'll try to give you a simple algorithm that you can implement:

1. sort the array
2. iterate from highest to lowest value
3. for each iteration, calculate the sum of each group, then add the element to the group with minimum sum

At the end of the loop you should have two fairly balanced arrays. Example:

Array: [1,5,5,6,7,10,20]
i1: `[20] []`
i2: `[20] [10]`
i3: `[20] [10,7]`
i4: `[20] [20,7,6]`
i5: `[20,5] [10,7,6]`
i6: `[20,5] [10,7,6,5]`
i7: `[20,5,1] [10,7,6,5]`

Where the sums are 26 and 28. As you can see we can further optimize the solution, if we exchange 5 and 6 resulting in [20,6,1] and [20,7,5,5] the sums are equal.

For this step you can:

1. find all groups of elements (x,y) where x is in group1, y is in group2, and |x-y| < |sum(group1) - sum(group2)|
2. loop all groups and try exchanging x with y until you get a minimum difference
3. after each exchange check if the minimum value in the group with the highest sum is higher then the difference of the groups, if so, transfer it to the other group

This algorithm will always return the best solution, and is a whole lot better then a greedy approach. However it is not optimal in terms of complexity, speed and memory. If one needs it for very large arrays and the resources are limited, the most optimal algorithm may differ depending on the speed/memory ration and the accepted error percentage.

Answer 4

This is a variation on the Partition Problem https://en.wikipedia.org/wiki/Partition_problem

If you want the optimal solution you have to test every possible combination of output sets. That may be feasible for small sets but is infeasible for large inputs.

One good approximation is the greedy algorithm I present below.

This heuristic works well in practice when the numbers in the set are of about the same size as its cardinality or less, but it is not guaranteed to produce the best possible partition.

First you need to put your input in a sortable collection such as a List.

1) Sort the input collection.

2) Create 2 result sets.

3) Iterate over the sorted input. If the index is even put the item in result1 else put the item in result2.

  List<Integer> input = new ArrayList<Integer>();
  Collections.sort(input);
  Set<Integer> result1 = new HashSet<Integer>();
  Set<Integer> result2 = new HashSet<Integer>();
  for (int i = 0; i < input.size(); i++) {
      if (i % 2 == 0) {// if i is even
          result1.add(input.get(i));
      } else {
          result2.add(input.get(i));
      }
  }

Answer 5

For this question, assume that we can divide the array into two subarrays such that their sum is equal. (Even thought they are not equal , it will work)

So if the sum of elements in array is S. Your goal is to find a subset with sum S/2. You can write a recursive function for this.

  int difference = Integer.MAX_VALUE;

  public void recursiveSum(int[] array, int presentSum, int index,Set<Integer> presentSet){
       if(index == array.length){
          if(Math.abs(presentSum - (S/2)) < difference)){
             difference = Math.abs(presentSum - (S/2);
             // presentSet is your answer
             return;
          }
       }
       recursiveSum(array,presentSum,index+1,presentSet); // don't consider the present element in the final solution
       presentSet.add(array[index]);
       recursiveSum(array,presentSum + array[index],index+1,presentSet); //consider the present element in the final solution

 }

You can also write an equivalent O(N^2) dynamic programming code for this. I was just demonstrating the idea.

So when you find this set with sum S/2, automatically you have divided the array in to two parts with same sum (S/2 here).