7
$\begingroup$

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?

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

The problem is known to be NP-complete: On the equal-subset-sum problem, Woeginger and Yu, IPL'92.

$\endgroup$
  • $\begingroup$ I think that paper proves that PARTITION is NP-complete. There's a straightforward reduction to the OP's problem, but it's not the same because of the three sets and non-emptiness constraints. $\endgroup$ – Huck Bennett Jul 8 '15 at 14:20
  • 8
    $\begingroup$ @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)$. $\endgroup$ – Peter Shor Jul 8 '15 at 14:38
  • $\begingroup$ @HuckBennett, what is the straightforward reduction? $\endgroup$ – Radu GRIGore Jul 8 '15 at 15:40
  • $\begingroup$ @Peter, Radu: You're right. Unfortunately I read both the OP's post and the abstract carelessly. $\endgroup$ – Huck Bennett Jul 8 '15 at 16:35
  • $\begingroup$ 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 $\endgroup$ – chazisop Jul 8 '15 at 16:49
1
$\begingroup$

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\})$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.