# Separated 3Sum versus 3Sum problem

Does it matter in the 3Sum problem if the numbers to be summed belong to the same set or to distinct sets?

Let's define

• the problem "$k$-Sum" as follows: given a single finite set of integers $X\subset N$ of size $n$, decide if there exists $k$ integers $x_1,\ldots,x_k\in X$ such that their sum $\sum_{i=1}^k x_i$ is null; and
• the problem "Separated $k$-Sum" as follows: given $k$ finite sets of integers $X_1,\ldots,X_k\subset N$ of respective sizes $n_1,\ldots,n_k\in[1..n]\subset N$, decide if there exist a vector $(x_1,\ldots,x_k)\in X_1\times\ldots\times X_k$ such that their sum $\sum_{i=1}^k x_i$ is null.

I was assuming that those two problems were equivalent, and I was using the second one as a pedagogical example for some parameterization technique (while there is an algorithm running in $O(n^2)$ for both, the second one can take advantage of variations in the size of the sets to solve the problem much faster, down to $O(n_1 n_3+\sum n_i\lg n_i)$ and $O(n_1 n_2 \lg \frac{n_3}{n_2}+\sum n_i\lg n_i)$).

But I realized today that I did not know how to prove this equivalence, and I might even start to think that they are not.

• Isn't 1a special case of 3? So in the worst case you cannot solve it faster than 3-SUM? – Kaveh Aug 29 '14 at 18:31
• @Kaveh: 1-SUM = Separated 1-SUM, but otherwise k-Sum is not a particular case of Separated k-Sum: if anything, the separation of X into subsets should only make the problem easier in limiting the number of solutions to consider. On the other hand, both have solutions running in time within $O(n^2)$. – Jeremy Aug 29 '14 at 20:47
• @Jeremy: Just pick $X_1 = X_2 = ... = X_k = X$ and you can solve k-SUM using SEPARATED k-SUM. For the opposite direction take a look to my answer. – Marzio De Biasi Aug 29 '14 at 20:53
• Have you checked Gajentaan and Overmars 1995? It is a must-read paper about 3SUM and related problems. – Tsuyoshi Ito Aug 30 '14 at 13:53
• @MarzioDeBiasi: how could I miss this? Thanks! – Jeremy Aug 31 '14 at 1:14

You can reduce the SEPARATED k-SUM problem to a (k+1)-SUM problem in the following way:

Given $X_1,...,X_n$, let $b$ such that $2^b > \max( abs(X_1) \cup ... \cup \;abs(X_n))$, where $abs(X_i) = \{ |x| \mid x \in X_i \}$, and let $c$ such that $2^c > k 2^b$

For $i = 1,...,k$ build $Y_i = \{ 2^{c+ki} + 2^{b} + x_j \mid x_j \in X_i \}$;
let $u = - \sum_{i=1}^k 2^{c+ki} -k2^b$

Build an equivalent (k+1)-SUM problem picking $X = \{ u \} \cup Y_1 \cup ... \cup Y_k$

Note that every $Y_i$ contains only positive elements.

Informally we require a $k+1$ elements subset $C$ from $X$ whose elements sum to zero. We cannot build a solution only with the negative element $u$; so we must include in $C$ at least one element $y$ from one of the $Y_i$; but the $2^{c+ki}$ "component" of $y$ can be balanced only if $u$ is also included; but including $u$ implies that exactly one of the elements of each $Y_i$ is included (the $- \sum_{i=1}^k 2^{c+ki}$ component of $u$ allows to keep the separation between the elements of the original $X_i$). But we also have $\sum_{j=1}^k (2^b + x_j) = k2^b$ and this implies that the original $x_j$s (coming from distinct $X_i$s as seen above) sum to zero.

• @Mario De Biasi: Should one correct s (not defined) into v (defined and unused) in the defintion of $X$? – Jeremy Aug 29 '14 at 21:02
• And also "But also the 2b component" should be "But also the 2^b component" – Jeremy Aug 29 '14 at 21:03
• @Jeremy: answer written too fast :-S, you're right; I fixed them ($v$ is used in the last part of the informal proof). Also note that the quantity $2^{c+ki}$ could be adjusted/optimized (e.g. replacing it with $2^{c+d(i-1)}$ where $d$ is the smaller integer such that $2^d > k$). – Marzio De Biasi Aug 29 '14 at 21:24
• @Jeremy: reading my answer again (?) I see that in fact you can use $\{u+v\}$ instead of $\{u,v\}$ ... in other words you can reduce the SEPARATED k-SUM to (k+1)-SUM – Marzio De Biasi Aug 29 '14 at 21:30
• @mario: Gajentaan and Overmars 1995 showed that 3SUM = Separated 3SUM. I will have to study more their proof, but maybe one can show that kSUM = Separated kSUM? – Jeremy Sep 1 '14 at 13:41