Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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

share|improve this question
    
recent news/ paper on 3SUM that looks at lower bounds on its decision tree complexity –  vzn Aug 19 at 15:16

4 Answers 4

up vote 17 down vote accepted

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

share|improve this answer
    
We need to keep track of which elements we are using right? because otherwise wouldn't [2,-1,-3,1000] give us 0 for 4 sum? –  sukunrt Dec 6 '13 at 13:40

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

share|improve this answer

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.

share|improve this answer

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.

share|improve this answer
1  
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 at 13:11
1  
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 at 17:19

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.