Dividing an integer array into two equal sized sub-arrays?

Question

I came across this question and couldn't find a reasonable solution. How would you divide an unsorted integer array into 2 equal sized sub-arrays such that, difference between sub-array sums is minimum.

For example: given an integer array a[N] (unsorted), we want to split the array into be split into a1 and a2 where a1.length == a2.length i.e N/2 and (sum of all numbers in a1 - sum of all numbers in a2) should be minimum.

For the sake of simplicity, let's assume all numbers are positve but there might be repetitions.

Answer 1

While others have mentioned that this is a case of the partition problem with modification, I'd like to point out, more specifically, that it is actually a special case of the minimum makespan problem with two machines. Namely, if you solve the two-machine makespan problem and obtain a value m, you obtain the minimum difference 2*m - sum(i : i in arr)

As the wikipedia article states, the problem is NP-complete for more than 2 machines. However, in your case, the List scheduling algorithm, which in general provides an approximate answer, is optimal and polynomial-time for the two-machine and three-machine case given a sorted list in non-increasing order.

For details, and some more theoretical results on this algorithm, see here.