6SUM: Given a set S of n integers, is there a subset of S with exactly 6 elements that sum to 0? How to do better than O(n^3)?

I've thought of this simple algorithm to solve the 6SUM problem which uses O(n^3) time and space: Generate all sets of triples and put them in a hash tab开发者_运维问答le where the key is the sum of the triples. Then iterate through the keys of the hash table: for each key k1, see if another key k2 exists such that k2 = S-k1

What's a more efficient algorithm? This is not a homework problem.

Your algorithm is Omega(n^6) in the worst case, it is only O(n^3) in the average case. You are ignoring the possibility of hash table collisions. You can make it O(n^3 logn) by using a balanced tree instead, though.

Also, this is in P, as there is a trivial polynomial time algorithm to check every possible combination of 6 numbers, so mention of knapsack etc is irrelevant.

Like the 3-SUM problem, I believe the r-sum problem having an algorithm which is o(n^[r/2]), (note: smallOH and [x] = greatest integer >= x, e.g. [5/2] = 3) is still open.

There is a brief mention of this in the 3-SUM page here, where there is a claim that the above bounds have been proven in restricted models of computation.

So getting better than O(n^3) (i.e. o(n^3)) might be an open problem.