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

CC BY-SA 3.0
2015-07-08T12:01:54.490Z
2015-07-08T12:08:49.593Z
2015-07-08T12:08:49.593Z
William Hoza
<p>The problem is known to be NP-complete: On the equal-subset-sum problem, Woeginger and Yu, IPL'92.</p>

CC BY-SA 3.0
2015-07-08T14:38:40.840Z
@Huck: Did you read [the abstract](http://www.sciencedirect.com/science/article/pii/002001909290226L) 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 
CC BY-SA 3.0
2015-07-08T15:40:23.170Z
@HuckBennett, what is the straightforward reduction?
Radu GRIGore
CC BY-SA 3.0
2015-07-08T16:35:36.383Z
@Peter, Radu: You're right. Unfortunately I read both the OP's post and the abstract carelessly.
Huck Bennett
CC BY-SA 3.0
2015-07-08T16:49:14.820Z
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](https://en.wikipedia.org/wiki/Karp's_21_NP-complete_problems) and figure 1, page 96, in the original [paper](http://cgi.di.uoa.gr/~sgk/teaching/grad/handouts/karp.pdf)
chazisop
CC BY-SA 3.0
2015-07-08T14:20:09.627Z
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.
Huck Bennett
CC BY-SA 3.0
2015-07-08T12:25:28.667Z
2015-07-08T12:25:28.667Z
JWM
<p>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$?</p>

<p>Is this problem NP-hard?</p>

<subset-sum>
"Any" Subset Sum. Is it hard?
Whosyourjay
# "Any" Subset Sum. Is it hard?

(Asked by: username_0 on 2015-07-08)

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?

**Tags:** subset-sum


---

## 2 answers

### Answer by username_2 on 2015-07-08. Score: 17 | Accepted answer

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

> **Comments:**
> **username_5**: 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.  
> **username_3**: @Huck: Did you read [the abstract](http://www.sciencedirect.com/science/article/pii/002001909290226L) 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)$.  
> **username_4**: @HuckBennett, what is the straightforward reduction?  
> **username_5**: @Peter, Radu: You're right. Unfortunately I read both the OP's post and the abstract carelessly.  
> **username_6**: 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](https://en.wikipedia.org/wiki/Karp's_21_NP-complete_problems) and figure 1, page 96, in the original [paper](http://cgi.di.uoa.gr/~sgk/teaching/grad/handouts/karp.pdf)  

---

### Answer by username_1 on 2015-07-08. Score: 1

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


---

