balanced 2-partition with equal cardinality (cardinality difference = 1 (max))

Question

Given a set $S$ of $N$ numbers, my aim is to partition it into two sets ($S_1$ and $S_2$), so that

(i) the difference $\sum S_1 - \sum S_2$ is minimized and

(ii) the difference $|S_1| - |S_2|$ is $1$ if $N$ is odd, and $0$ if $N$ is even.

I am able to come up with a dynamic programming algorithm (inspired by dp - knapsack) using a two-dimensional array; however I am unable to keep track of the elements in a particular set and hence am not able to pass some typical cases.

Can anyone please suggest me what approach should I look into to solve this problem?

Any pointers are helpful.

Thanking You, Dj

Answer 1

If you actually mean the difference $\sum S_1 - \sum S_2$, then just pick the largest $N/2$ numbers for $S_2$, and the smallest $N/2$ numbers for $S_1$.

If you mean the absolute difference (which is more likely), then there is an easy reduction from SUBSET-SUM showing that the decision variant of this problem is NP-complete. Conceivably you can find a very similar problem in the approximation algorithm literature - this would tell you how well an efficient algorithm can approximate the optimum.