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

3 Answers 3

up vote 15 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

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.