Generalised 3SUM (k-SUM) problem?

Question

The 3SUM problem tries to identify 3 integers $a,b,c$ from a set $S$ of size $n$ such that $a + b + c = 0$.

It is conjectured that there is not better solution than quadratic, i.e. $\mathcal{o}(n^2)$. Or to put it differently: $\mathcal{o}(n \log(n) + n^2)$.

So I was wondering if this would apply to the generalised problem: Find integers $a_i$ for $i \in [1..k]$ in a set $S$ of size $n$ such that $\sum_{i \in [1..k]} a_i = 0$.

I think you can do this in $\mathcal{o}(n \log(n) + n^{k-1})$ for $k \geq 2$ (it's trivial to generalise the simple $k=3$ algorithm).
But are there better algorithms for other values of $k$?

Answer 1

$k$-SUM can be solved more quickly as follows.

• For even $k$: Compute a sorted list $S$ of all sums of $k/2$ input elements. Check whether $S$ contains both some number $x$ and its negation $-x$. The algorithm runs in $O(n^{k/2}\log n)$ time.

• For odd $k$: Compute the sorted list $S$ of all sums of $(k-1)/2$ input elements. For each input element $a$, check whether $S$ contains both $x$ and $-a-x$, for some number $x$. (The second step is essentially the $O(n^2)$-time algorithm for 3SUM.) The algorithm runs in $O(n^{(k+1)/2})$ time.

Both algorithms are optimal (except possibly for the log factor when $k$ is even and bigger than $2$) for any constant $k$ in a certain weak but natural restriction of the linear decision tree model of computation. For more details, see:

• Nir Ailon and Bernard Chazelle. Lower bounds for linear degeneracy testing. JACM 2005.

• Jeff Erickson. Lower bounds for linear satisfiability problems. CJTCS 1999.

Answer 2

$d$-SUM requires time $n^{\Omega(d)}$ unless k-SAT can be solved in $2^{o(n)}$ time for any constant k. This was shown in a paper by Mihai Patrascu and Ryan Williams(1).

In other words, assuming the exponential time hypothesis, your algorithm is optimal up to a constant factor in the exponent (a polynomial factor in $n$)

(1) Mihai Patrascu and Ryan Williams. On the Possibility of Faster SAT Algorithms. Proc. 21st ACM/SIAM Symposium on Discrete Algorithms (SODA2010)

Answer 3

Here are a few simple observations.

For $k=1$, you can do it in $\Theta(n)$ time by scanning the array for a zero. For $k=2$, you can do it without hashing in $\Theta(n \log n)$ time. Sort the array and then scan it. For each element $i$ do a binary search for $-i$. This results in total complexity of $\Theta(n \log n)$. For the case $k=n$ you can do it in $\Theta(n)$ time by accumulating the array and checking the result.

For some more references, see The Open Problems Project page for 3SUM.

Answer 4

See http://arxiv.org/abs/1407.4640

A new algorithm for solving the rSUM problem Valerii Sopin

Abstract:

A determined algorithm is presented for solving the rSUM problem for any natural r with a sub-quadratic assessment of time complexity in some cases. In terms of an amount of memory used the obtained algorithm has also a sub-quadratic order. The idea of the obtained algorithm is based not considering integer numbers, but rather k∈N successive bits of these numbers in the binary numeration system. It is shown that if a sum of integer numbers is equal to zero, then the sum of numbers presented by any k successive bits of these numbers must be sufficiently "close" to zero. This makes it possible to discard the numbers, which a fortiori, do not establish the solution.

It's something new in this issue.