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?

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

2 Answers 2


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

  • $\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$ Commented Jul 8, 2015 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$ Commented Jul 8, 2015 at 14:38
  • $\begingroup$ @HuckBennett, what is the straightforward reduction? $\endgroup$ Commented Jul 8, 2015 at 15:40
  • $\begingroup$ @Peter, Radu: You're right. Unfortunately I read both the OP's post and the abstract carelessly. $\endgroup$ Commented Jul 8, 2015 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
    Commented Jul 8, 2015 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\})$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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