Split array into two subsets with minimum difference

general
, ,
1

Given an array containing N numbers, we need to split the array into two subsets, such that each subset contains N/2 numbers, and the difference between the sum of the two subsets is minimised. I was able to come up with this :

A[i][j][k] = 1 if there is a subset of size ‘k’ of the first ‘i’ elements that has sum ‘j’. Fill this, and then check A[N][j][N/2] for all j and pick whichever minimises the difference. I want to know if there is a faster way of doing this.

2 Likes
2

I think a greedy approach might work, though I dont know any proof.
Start picking elements one by one. Keep track of the difference sum sa, sb for 2 sets A and B. Now put a element in first set if it minimizes |sa-sb| else put it in the other set.

3

That would probably give different solutions for different orderings of the input array. I tried taking the numbers in the sorted order and then doing exactly what you mentioned, but it doesn’t work (try {1,2,3,4} as the input) :confused: what seems to be minimising the difference at some point might not be optimal overall.

2 Likes
4

It may be done like this
each time either pick the element or not and do this until you have N/2 elements and when you have picked N/2 elements then do this
ans = min( ans, (sum_of_N_elems - sum_of_cur_N/2_elems) ).
With this method you have to traverse many paths and complexity will be high so you can use dynamic programming to reduce complexity.

5

Sort array in decreasing order. create 2 array of n/2 max size. insert element into those array using below condition.

for element in array:
    if sum(array1)<=sum(array2):
        if array1 is not full:
            array1.append(element)
        else:
            array2.append(element)
    else:
        if array2 is not full:
            array2.append(element)
        else:
            array1.append(element)

for maximum cases it will give you correct result and for other will give close result.

Another method is to try for all possible combination which is, of course, very slow.

1 Like
6

Sorry ,i know its a bit late to ask,bt can u tell the constraint for n,a[i]?(assuming a is array)

7

This question was asked in an interview, the interviewer didn’t mention any constraints.