# “Any” Subset Sum. Is it hard?

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?

• This answer is somewhat related. $\;$ – user6973 Jul 8 '15 at 17:25

• @Huck: Did you read the abstract of the paper? That paper appears to be the exact same problem as the OP is asking. Let $S_3 = S - (S_1 \cup S_2)$. – Peter Shor Jul 8 '15 at 14:38
• Also, for the sake of historical accuracy, PARTITION was known to be $\mathbb{NP}$-complete at least since Karp's list of 21 problems, as a special (but still hard to solve) case of KNAPSACK. See wikipedia and figure 1, page 96, in the original paper – chazisop Jul 8 '15 at 16:49
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\})$.