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.

  • $\begingroup$ Isn't 1a special case of 3? So in the worst case you cannot solve it faster than 3-SUM? $\endgroup$
    – Kaveh
    Aug 29, 2014 at 18:31
  • $\begingroup$ @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)$. $\endgroup$
    – J..y B..y
    Aug 29, 2014 at 20:47
  • 3
    $\begingroup$ @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. $\endgroup$ Aug 29, 2014 at 20:53
  • 1
    $\begingroup$ Have you checked Gajentaan and Overmars 1995? It is a must-read paper about 3SUM and related problems. $\endgroup$ Aug 30, 2014 at 13:53
  • $\begingroup$ @MarzioDeBiasi: how could I miss this? Thanks! $\endgroup$
    – J..y B..y
    Aug 31, 2014 at 1:14

1 Answer 1


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.

  • $\begingroup$ @Mario De Biasi: Should one correct s (not defined) into v (defined and unused) in the defintion of $X$? $\endgroup$
    – J..y B..y
    Aug 29, 2014 at 21:02
  • $\begingroup$ And also "But also the 2b component" should be "But also the 2^b component" $\endgroup$
    – J..y B..y
    Aug 29, 2014 at 21:03
  • $\begingroup$ @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$). $\endgroup$ Aug 29, 2014 at 21:24
  • $\begingroup$ @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 $\endgroup$ Aug 29, 2014 at 21:30
  • $\begingroup$ @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? $\endgroup$
    – J..y B..y
    Sep 1, 2014 at 13:41

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.