0
$\begingroup$

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

1 Answers 1