How to separate range of integers into two equal parts

Question

I have an array of integers like this one

int [] num = {5, 8, 1, 1, 2, 3, 2}

and I want to divide it into 2 parts, so that the total of 2 sets will be as equal as possible: (output)

SET 1: 5 Piece(s)
1
1
2
2
5
Total: 11

SET 2: 2 Piece(s)
8
3
Total: 11

another example is

int [] num = {4, 6, 1, 2, 3, 3, 4}

with output like this:

SET 1: 3 Piece(s)
3
4
4
Total: 11

SET 2: 4 Piece(s) 
6
1
2
3
Total: 12

any help? =) thanks

Answer 1

If the array is not too long, try a lazy solution: brute-force. Since all you need is to separate it into two sets, you'll need to check 2^n possibilities, because a number is either in the first set or not (i.e. in the second set).

Here's a sample code I just wrote:

public static int[][] bruteForce(int[] input) {
    int n = input.length;
    int[][] res = new int[2][n];
    int minVal = Integer.MAX_VALUE;
    int iMinVal = 0;
    int limit = (int) Math.pow(2, n);

    for (int i = 0; i < limit; i++) {
        int v = i;
        int diff = 0;
        for (int j = 0; j < n; j++) {
            diff = diff + ((v & 1) == 0 ? +1 : -1) * input[j];
            v = v >> 1;
        }
        if (Math.abs(diff) < minVal) {
            iMinVal = i;
            minVal = Math.abs(diff);
        }
    }

    int a = 0, b = 0;
    for (int i = 0; i < n; i++) {
        if ((iMinVal & 1) == 0) {
            res[0][a++] = input[i];
        } else {
            res[1][b++] = input[i];
        }
        iMinVal = iMinVal >> 1;
    }

    return res;
}

public static void main(String[] args) {
    int[] num = {5 ,8 ,1 ,1 ,2 ,3 ,2};
    int[] num2 = {4, 6, 1, 2, 3, 3, 4};

    int[][] r = bruteForce(num);
    System.out.println("First example:");
    System.out.println(Arrays.toString(r[0])+ ", sum = "+Arrays.stream(r[0]).sum());
    System.out.println(Arrays.toString(r[1])+ ", sum = "+Arrays.stream(r[1]).sum());

    r = bruteForce(num2);
    System.out.println("Second example:");
    System.out.println(Arrays.toString(r[0])+ ", sum = "+Arrays.stream(r[0]).sum());
    System.out.println(Arrays.toString(r[1])+ ", sum = "+Arrays.stream(r[1]).sum());
}

output:

First example:
[5, 1, 3, 2, 0, 0, 0], sum = 11
[8, 1, 2, 0, 0, 0, 0], sum = 11
Second example:
[2, 3, 3, 4, 0, 0, 0], sum = 12
[4, 6, 1, 0, 0, 0, 0], sum = 11

If the length of the array is big, then I guess try some smart brute-force, or other methods. Like, sorting the array into non-ascending order, then starting from the biggest value, put each value into the array with less sum, which in the current case give the right answer:

public static int[][] alternative(int[] input) {
    int n = input.length;
    int[][] res = new int[2][n];

    int[] input0 = Arrays.copyOf(input, n);

    Arrays.sort(input0);

    System.out.println("Input: "+Arrays.toString(input)+", ordered: "+Arrays.toString(input0));

    int sum1 = 0, sum2 = 0;
    int a = 0, b = 0;

    for (int i = n-1; i >= 0; i--) {
        if (sum1 <= sum2) {
            res[0][a++] = input0[i];
            sum1 = sum1 + input0[i];
            System.out.println("Adding "+input0[i]+" into set 1 ==> Sum1 = "+sum1);
        } else {
            res[1][b++] = input0[i];
            sum2 = sum2 + input0[i];
            System.out.println("Adding "+input0[i]+" into set 2 ==> Sum2 = "+sum2);
        }
    }
    return res;
}

output:

First example:
Input: [5, 8, 1, 1, 2, 3, 2], ordered: [1, 1, 2, 2, 3, 5, 8]
Adding 8 into set 1 ==> Sum1 = 8
Adding 5 into set 2 ==> Sum2 = 5
Adding 3 into set 2 ==> Sum2 = 8
Adding 2 into set 1 ==> Sum1 = 10
Adding 2 into set 2 ==> Sum2 = 10
Adding 1 into set 1 ==> Sum1 = 11
Adding 1 into set 2 ==> Sum2 = 11
[8, 2, 1, 0, 0, 0, 0], sum = 11
[5, 3, 2, 1, 0, 0, 0], sum = 11

Second example:
Input: [4, 6, 1, 2, 3, 3, 4], ordered: [1, 2, 3, 3, 4, 4, 6]
Adding 6 into set 1 ==> Sum1 = 6
Adding 4 into set 2 ==> Sum2 = 4
Adding 4 into set 2 ==> Sum2 = 8
Adding 3 into set 1 ==> Sum1 = 9
Adding 3 into set 2 ==> Sum2 = 11
Adding 2 into set 1 ==> Sum1 = 11
Adding 1 into set 1 ==> Sum1 = 12
[6, 3, 2, 1, 0, 0, 0], sum = 12
[4, 4, 3, 0, 0, 0, 0], sum = 11

For the 0s in the output, you can just write a simple function that create a new arrays without the 0s.

Answer 2

Have a for loop to loop like:

int sum =0:
for(int I=0; I<num.length/2; I++){
System.out.println(num[i]);
sum=sum+num[i];
}
System.out.println(sum);

(Written on ipad excuse any mistakes plz.

Answer 3

We should try with all combinations. For example, if the array is (1,1,100,100), then answer is (100,1) (100,1). If the array is (1,1,50,100) then answer is (1,1,50) (100). I don't think there is any short cut to this. If the array has N elements, then we shall try all combinations (Nc1, NcN01), (Nc2, NcN-2) .. and so on. Then find which of their difference is least.