# 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
Commented Aug 19, 2014 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 Commented Aug 21, 2019 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. Commented Aug 21, 2019 at 17:34
• I'm familiar with solving 2-Sum in O(n) time using two pointers. Can you tell me how this solution avoids picking the same number twice? For eg, consider the list A = [-7,0,7,1] for 4-Sum. You can have a sorted list S of all sums of 2 input elements: {-7,-6,0,1,7,8}. You will see that both 7 and -7 exist in S and sum to zero. However, there's no set of four elements in the original array that also sum to zero. This is easy if the numbers in A are unique (See stackoverflow.com/a/14732368/2715997), but I am wondering how to avoid picking a number twice when numbers are repeated in A. Commented Nov 6, 2020 at 10:16
• @ApoorvGupta it's just bookkeeping. Sort the input set and remove duplicates (so it's a set). Compute the sorted list S of pairwise sums preserving duplicates, and record for each sum the indices of the elements that generated it. For any pairwise sum x, each index is used at most once. Suppose S contains both x and -x. If either x or -x appears in S more than twice, we can immediately return TRUE. Otherwise, we can check for a disjoint pair of index pairs in O(1) time. Commented Nov 6, 2020 at 18:08
• The problem statement specifies an input SET. A1 and A2 are the same set. Commented Nov 11, 2020 at 3:45

$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. Commented Aug 19, 2014 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.) Commented Aug 19, 2014 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.
Commented Feb 22, 2019 at 8:04