# Generalised 3SUM (k-SUM) problem?

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$?

• recent news/ paper on 3SUM that looks at lower bounds on its decision tree complexity – vzn Aug 19 '14 at 15:16

$$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:

• stackoverflow.com/a/14737071/511736 suggest O(n^2) algorithm when k=4 – Kowser Aug 21 at 3:18
• Hashing is cheating. The algorithm described at StackOverflow only runs in O(n^2) time for integer input, and only with high probability, and only if you use an appropriate random hash function. The algorithms in my answer work in the real RAM model, they're completely deterministic, and the time bounds are worst-case. You can also shave off log-factors in the integer setting using "bit tricks", but that's kinda boring. – JeffE Aug 21 at 17:34

$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)

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.

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.

• Could you explicitly cite the results from the article that are relevant to the question? (Pasting the abstract may be ok, if the article is relevant as a whole.) Posts on SE are supposed to be more than just a link. – FrankW Aug 19 '14 at 13:11
• As it is, this answer is a (potentially useful) comment, not an answer. As such it would have to contain some original content, e.g. your describing the algorithm in your own words. Do you want to do that? I can convert your answer to a comment if you don't. (I'm aware that you could not comment due to your rep.) – Raphael Aug 19 '14 at 17:19
• That does not look like a credible paper. The claim "time complexity sub-quadratic in some cases" is not a useful statement. Time complexity is by definition the worst-case running time. Bubble sort runs in linear time in some cases, but its time complexity remains quadratic. – D.W. Feb 22 at 8:04