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

<p>Given $X_1,...,X_n$, let $b$ such that $2^b &gt; \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 &gt; k 2^b$ </p>

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

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

<p>Note that every $Y_i$ contains only positive elements.</p>

<p>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.</p>

CC BY-SA 3.0
2014-08-29T21:02:03.847Z
@Mario De Biasi: Should one correct s (not defined) into v (defined and unused) in the defintion of $X$?
J.y B.y
CC BY-SA 3.0
2014-08-29T21:03:33.253Z
And also "But also the 2b component" should be "But also the 2^b component"
J.y B.y
CC BY-SA 3.0
2014-08-29T21:24:48.330Z
@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
CC BY-SA 3.0
2014-08-29T21:30:14.780Z
@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
CC BY-SA 3.0
2014-09-01T13:41:43.107Z
@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?
J.y B.y
CC BY-SA 3.0
2014-08-29T20:36:25.397Z
2014-08-29T21:33:46.173Z
2014-08-29T21:33:46.173Z
Marzio De Biasi
<p>Does it matter in the 3Sum problem if the numbers to be summed belong to the same set or to distinct sets?</p>

<p>Let's define </p>

<ul>
<li>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 </li>
<li>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.  </li>
</ul>

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

<p>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. </p>

CC BY-SA 3.0
2014-08-29T18:31:45.167Z
Isn't 1a special case of 3? So in the worst case you cannot solve it faster than 3-SUM?
Kaveh
CC BY-SA 3.0
2014-08-29T20:47:22.370Z
@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)$.
J.y B.y
CC BY-SA 3.0
2014-08-29T20:53:39.057Z
@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
CC BY-SA 3.0
2014-08-30T13:53:20.117Z
Have you checked [Gajentaan and Overmars 1995](http://dx.doi.org/10.1016/0925-7721%2895%2900022-2)?  It is a must-read paper about 3SUM and related problems.
Tsuyoshi Ito
CC BY-SA 3.0
2014-08-31T01:14:57.633Z
@MarzioDeBiasi: how could I miss this? Thanks!
J.y B.y
CC BY-SA 3.0
2014-08-31T01:44:18.743Z
@TsuyoshiIto: reviewing it now, thanks also!
J.y B.y
<ds.algorithms>
Separated 3Sum versus 3Sum problem
J.y B.y
# Separated 3Sum versus 3Sum problem

(Asked by: username_0 on 2014-08-29)

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.

**Tags:** ds.algorithms

> **Comments:**
> **username_1**: Isn't 1a special case of 3? So in the worst case you cannot solve it faster than 3-SUM?  
> **username_0**: @username_1: 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)$.  
> **username_2**: @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.  
> **username_3**: Have you checked [Gajentaan and Overmars 1995](http://dx.doi.org/10.1016/0925-7721%2895%2900022-2)?  It is a must-read paper about 3SUM and related problems.  
> **username_0**: @MarzioDeBiasi: how could I miss this? Thanks!  
> **username_0**: @TsuyoshiIto: reviewing it now, thanks also!  

---

## 1 answers

### Answer by username_2 on 2014-08-29. Score: 4 | Accepted answer

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.

> **Comments:**
> **username_0**: @Mario De Biasi: Should one correct s (not defined) into v (defined and unused) in the defintion of $X$?  
> **username_0**: And also "But also the 2b component" should be "But also the 2^b component"  
> **username_2**: @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$).  
> **username_2**: @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  
> **username_0**: @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?  

---

