Sum numbers as two groups such that the difference is minimum

general
, ,
1

So the problem statement(http://opc.iarcs.org.in/index.php/problems/EQGIFTS) is: given n pairs of integers, group them into two sets such that each number from a pair goes to one set so as to minimize the difference between their sums.
I broke that down into differences in each pair. Now I have to make two groups out of them to minimize difference between sums.
My approach:
1)Arrange the differences in ascending order
2)Pass the array and n to a function which should return the required output.
function(array_pointer, n):
1)If n==1, return the only element. If n==2, return their difference.
2)Take last two differences and find the (abs value) of difference of the differences.
3)Insert the difference in the sorted array so as to preserve the order.
4)return function(array_pointer, n-1).

It passed 40% of the test cases and I cant think of a test case where it would fail. Can anyone help me here?

2

You can look into this link . It has a nice explanation for this type of problem .

3

The solution is nice and I am just wondering if that can also be done with a 1d array itself than a table. Also it would be helpful to know a test case where my method fails.

4

The constraints on the problem are small enough to use this method and I think the problem setter intends to do it by this way .I don’t think this can be done in 1D array .