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;
}
}

@LuigiCortese: I was trying to first sort the array. Then start putting one number in one group, another number in another group, and so on, till then end. But it didn't seem to work. — shanti, Jul 04 '15 at 16:51

Alexandru Severin · Answer 1 · 2015-07-05T10:20:17.403

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:

sort the array
iterate from highest to lowest value
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:

find all groups of elements (x,y) where x is in group1, y is in group2, and |x-y| < |sum(group1) - sum(group2)|
loop all groups and try exchanging x with y until you get a minimum difference
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.

Hi Alexa, thanks a lot for the answer. After looking at your solution, I felt like it will work for most cases (assuming no repeated number and a unique solution), so I thought to give it a try. But it seems, there needs to be some more steps apart from the last 2 steps you have mentioned. I tried it with a java program, it did work for a specific set of no. but failed for another. Following program, worked for [1,3,5,9] but failed for [4,3,5,9, 11]. Could you please have a look at the program below and suggest what mistake I am doing. Putting it as a separate comment. — shanti, Jul 04 '15 at 21:19

bhspencer · Answer 2 · 2015-07-04T17:29:01.783

2

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));
      }
  }

edited Jul 04 '15 at 17:29

answered Jul 04 '15 at 16:57

bhspencer

13,086
5
35
44

Thanks for the answer. But by this way, won't [5,4,8,2] get divided into [5] and [2,4,8] ? And then the difference becomes 9. – shanti Jul 04 '15 at 17:02
No. The test if even is on the index (position) of the item not value of the item. The input will sorted to [2,4,5,8] and the output will be [2,5] and [4,8] – bhspencer Jul 04 '15 at 17:08
Note that this algorithm will only provide an approximation of the solution not the optimal solution. It will work best on larger inputs. – bhspencer Jul 04 '15 at 17:08
Which is not the correct answer. This is a very bad solution for this problem. – Alexandru Severin Jul 04 '15 at 17:09
Which is why I said it is an approximation. If you want the optimal solution you have to test every possible combination of output sets which is is an NP-complete problem. – bhspencer Jul 04 '15 at 17:11
@bhspencer: Oh Sorry for that miss. But still, your solution will fail for [1,3,5,9]. It will divide them as [1,5] and [3,9], which is not the correct solution. – shanti Jul 04 '15 at 17:14
Yes it will not give the correct answer on very small sets. I recognize that. However the above solution is generally recognized as a useful approximation https://en.wikipedia.org/wiki/Partition_problem – bhspencer Jul 04 '15 at 17:15
I got this question in an online test of a very reputed US financial firm. If it has got no specific solution, I wonder why was the problem given! :/ – shanti Jul 04 '15 at 17:29
It is possible to write an optimal solution, its just that for large sets it will take an extremely long time to produce the result. That is why approximations for this type of problem are considered acceptable. – bhspencer Jul 04 '15 at 17:30
hmmm ok. May be they just wanted to see how good effort I can put in trying to write the program – shanti Jul 04 '15 at 17:31

shanti · Accepted Answer · 2015-07-05T15:08:46.133

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;
}
}

Why do you think its not working for `zero or repeted numbers`? I just ran it with `[0,0,2,2,3]` and it results `[0,0,3] [2,2]`. I don't see any error or better solution — Alexandru Severin, Jul 05 '15 at 09:58
@AlexandruSeverin: Thanks for checking the code. I hadn't checked for repeated numbers. I had just thought that either of repeated number or a 0, would cause multiple solution. But It looks I was wrong. Repeated number doesn't necessarily mean non-unique solution. And this program does seem to work for repeated numbers too (which I feel really great about!!) :) But presence of a 0 would mean there would be two solution. In whichever set you put the 0, it doesn't matter. So if unique solution is assumed, then 0 can't be considered. Thanks for all the great help. I guess this program looks great — shanti, Jul 05 '15 at 10:12
I assumed you need `a` best solution, if you need `all` possible solutions with the minim difference you could make for each step a list of solutions, if you find a better solution, reset the list. if you find a equal difference solution, add it to the list. Then apply the next step for each solution found iteratively — Alexandru Severin, Jul 05 '15 at 10:28
@AlexandruSeverin I agree, all possible set of solutions satisfying the condition (min diff), can be easily found out now. I will try tweaking a bit the same code to achieve the same. But anyway, that was not the major issue. The question I had encountered, clearly mentioned to assume unique solution. In case of non-unique solution, this program will simply get the first solution that it gets, and will ignore the later possible ones. But yes, thanks for the hint. Whenever I get free, I will try modifying the code to get all possible set of solutions. — shanti, Jul 05 '15 at 10:48
Wrong answer for input [616,202,595,876,388,120,238,296] Output = 87 Expected = 15 — harshlal028, Dec 21 '17 at 19:04

ikk · Answer 4 · 2015-07-05T12:28:57.683

0

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.

edited Jul 05 '15 at 12:28

answered Jul 04 '15 at 17:12

ikk

123
3
14

tried this code on a sample set- [1,3,5,9] It doesn't work. I got two arrays- [1,5] and [3,9] – shanti Jul 04 '15 at 19:32
sort the initial array in descending order. – ikk Jul 05 '15 at 12:28
Now it fails for [4,3,5,9,11]. I get [11,4] [9,5,3], which is wrong. But strangely, for many other sets, it is giving correct output! May be a little correction will make it work perfectly. – shanti Jul 05 '15 at 15:07

Karthik · Answer 5 · 2015-07-04T17:22:41.907

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).

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

5 Answers5

Linked