Minimum set difference

Question

i came across this question on this website called codility, but i cant really figure out how to solve it, would appreciate the help

Given an array A of n integers, and the sequence S of n elements 1 or -1 we define the value:

Assume the sum of zero elements is equal zero. Write a function

int min_abs_sum(int[] A);

than given an array A of n integers from the range [-100..100] computes the lowest possible value of val(A,S) (for any sequence S with elements 1 or -1). You can assume that n<=20000 .

For example given array: a={1,5,2,-2}

your function should return 0, since for sequence S=(-1,1,-1,1) the val(A,S)=0.

Here are two links for some peoples result, it doesnt show the solution but it does show the complexity of their algorithms, the first link shows the complexity at which the program should run and the second one is slower.

1st link 100% marks

2nd link 86% marks

Answer 1

This is poorly worded version of the partition problem. You are going to split the array A into 2 groups as close to equal as possible. The one with the larger sum you'll be assigning +1 in the S array, and the other group will get -1. Pick a solution to the partition problem and adjust it to return an answer to this one. Actually it's the variant of partition that seeks the best possible value as opposed to 2 equal sets.

EDIT here is some python code based on the paper linked by @Jerry Coffin

def min_abs_sum(A):
vals = []
for x in A:
    for v in vals:
        n = v+x
        if (abs(n)<=1000000) and (n not in vals): vals.append(n)
        n = v-x
        if (abs(n)<=1000000) and (n not in vals): vals.append(n)
    if (x not in vals): vals.append(x)
    if (-x not in vals): vals.append(-x)
return (min([abs(x) for x in vals]))

The one million value is half of 20000 (max numbers in A) times 100/2. I've used a list instead of an array, which means some things will be faster and some slower than what they do in the paper. It is conceivable that the min is achieved by summing the first half of the numbers and subtracting the second half - or something like that which requires large intermediate sums. I'm using a list rather than an array, but the size is still bounded. Sorry, I don't do Java.