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