Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.
Sign up to join this community
Here is a variant of the classic partition problem: Given a list of integers can it be partitioned into $S_1$, $S_2$, and $S_3$, with $S_1$ and $S_2$ nonempty, so the sum of elements in $S_1$ equals the sum of elements in $S_2$?
Is this problem NP-hard?
The problem is known to be NP-complete: On the equal-subset-sum problem, Woeginger and Yu, IPL'92.
I don't know. Using dynamic programming, we can solve this problem in pseudo-polynomial time $O(nN)$, where $n$ is the number of integers in the list and $N$ is the sum of all integers in the list, as follows. For $m \leq n$, $|M| \leq N$, and $c \in \{\emptyset, \{1\}, \{2\}, \{1, 2\}\}$, let $T(m, M, c)$ tell whether it is possible to partition the first $m$ integers into sets $S_1, S_2, S_3$, so that $(\sum S_2) - (\sum S_1) = M$, and $S_i$ is nonempty for every $i \in c$. Say the integers are $x_1, \dots, x_n$. We have the recurrence $$ T(m, M, c) = T(m - 1, M, c) \vee T(m - 1, M + x_m, c \setminus \{1\}) \vee T(m - 1, M - x_m, c \setminus \{2\}). $$ (We can choose to put $x_m$ in $S_3$, or in $S_1$, or in $S_2$.) From here, the straightforward DP algorithm gives us every value of $T(m, M, c)$ in time $O(nN)$; the answer to the problem is $T(n, 0, \{1, 2\})$.
