Challenge details

Description

In computational complexity theory, the 3SUM problem asks if a given set of n real numbers contains three elements that sum to zero. A naive solution works in O(N2) time, and research efforts have been exploring the lower complexity bound for some time now.

Input example

You will be given a list of integers, one set per line. Example:

9 -6 -5 9 8 3 -4 8 1 7 -4 9 -9 1 9 -9 9 4 -6 -8

Output example

Your program should emit triplets of numbers that sum to 0. Example:

-9 1 8
-8 1 7
-5 -4 9
-5 1 4
-4 1 3
-4 -4 8

Challenge input

4 5 -1 -2 -7 2 -5 -3 -7 -3 1
-1 -6 -3 -7 5 -8 2 -8 1
-5 -1 -4 2 9 -9 -6 -1 -7

Challenge output

-7 2 5
-5 1 4
-3 -2 5
-3 -1 4
-3 1 2

-7 2 5
-6 1 5
-3 1 2

-5 -4 9
-1 -1 2

---

Notes, ideas, additional information

Reddit page