Divide an Array in equal size, such that value of given function is minimum

Question

I've came across the following problem statement.

You have a list of natural numbers of size N and you must distribute the values in two lists A and B of size N/2, so that the squared sum of A elements is the nearest possible to the multiplication of the B elements.

Example: Consider the list 7 11 1 9 10 3 5 13 9 12.
The optimized distribution is:
List A: 5 9 9 12 13
List B: 1 3 7 10 11
which leads to the difference abs( (5+9+9+12+13)^2 - (1*3*7*10*11) ) = 6
Your program should therefore output 6, which is the minimum difference that can be achieved.

What I've tried:

I've tried Greedy approach in order to solve this problem. I took two variables sum and mul. Now I started taking elements from the given set one by one and tried adding it in both the variables and calculated current square of sum and multiplication. Now finalize the element in one of the two sets, such that the combination gives minimum possible value.

But this approach is not working in the given example itselt. I can't figure out what approach could be used here.

I'm not asking for exact code for the solution. Any possible approach and the reason why it is working, would be fine.

EDIT:

Source: CodinGame, Community puzzle

Answer 1

Try out this:

import java.util.Arrays;

public class Test {

    public static void main(String [] args){
        int [] arr = {7, 11, 1, 9, 10, 3, 5, 13, 9, 12}; 
        int [][] res = combinations(5, arr);
        int N = Arrays.stream(arr).reduce(1, (a, b) -> a * b);
        int min = Integer.MAX_VALUE; 
        int [] opt = new int [5];
        for (int [] i : res){
            int k = (int) Math.abs( Math.pow(Arrays.stream(i).sum(), 2) - N/(Arrays.stream(i).reduce(1, (a, b) -> a * b)));
            if(k < min){
                min = k;
                opt = i;
            }
        }
        Arrays.sort(opt);
        System.out.println("minimum difference is "+ min + " with the subset containing this elements " + Arrays.toString(opt));
    }

    // returns all k-sized subsets of a n-sized set 
    public static int[][] combinations(int k, int[] set) {
        int c = (int) binomial(set.length, k);
        int[][] res = new int[c][Math.max(0, k)];
        int[] ind = k < 0 ? null : new int[k];
        for (int i = 0; i < k; ++i) { 
            ind[i] = i; 
        }
        for (int i = 0; i < c; ++i) {
            for (int j = 0; j < k; ++j) {
                res[i][j] = set[ind[j]];
            }
            int x = ind.length - 1;
            boolean loop;
            do {
                loop = false;
                ind[x] = ind[x] + 1;
                if (ind[x] > set.length - (k - x)) {
                    --x;
                    loop = x >= 0;
                } else {
                    for (int x1 = x + 1; x1 < ind.length; ++x1) {
                        ind[x1] = ind[x1 - 1] + 1;
                    }
                }
            } while (loop);
        }
        return res;
    }
    // returns n choose k; 
    // there are n choose k combinations without repetition and without observance of the sequence
    // 
    private static long binomial(int n, int k) {
        if (k < 0 || k > n) return 0;
        if (k > n - k) {
            k = n - k;
        }
        long c = 1;
        for (int i = 1; i < k+1; ++i) {
            c = c * (n - (k - i));
            c = c / i;
        }
        return c;
    }
}

Code taken from this stackoverflow answer, also take a look at this wikipedia article about Combinations.