## 3SUM

### June 18, 2013

Today’s exercise is a classic problem of computer science: given an array of positive and negative integers, find three that sum to zero, or indicate that no such triple exists. This is similar to the subset sum problem, which we solved in a previous exercise, but simpler because of the limit to three items. A brute force solution that operates in O(n3) time uses three nested loops to select items from the array and test their sum, but an O(n2) solution exists. For instance, in the array [8, -25, 4, 10, -10, -7, 2, -3], the numbers -10, 2 and 8 sum to zero, as do the numbers -7, -3, and 10.

Your task is to write a program that solves the 3SUM problem in O(n2) time. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

### 7 Responses to “3SUM”

1. […] today’s Programming Praxis exercise, our goal is to find all groups of three numbers in a given list that […]

```import Data.List
import qualified Data.IntSet as I

sum3 :: [Int] -> [[Int]]
sum3 xs = nub [sort [a,b,-a-b] | (a:bs) <- tails xs, b <- bs, I.member (-a-b) s]
where s = I.fromList xs
```
3. Jussi Piitulainen said

Accepting (-1,2,-1) or (0,0,0) as a solution if -1 or 0 occurs in the bag more than once or twice, respectively. This produces all permutations, including duplicates if a solution contains duplicate elements. Python’s True and False appear to count as 1 and 0.

```from collections import Counter
def threesums(bag):
c = Counter(bag)
for j, m in enumerate(bag):
for k, w in enumerate(bag):
if j == k: continue
if c[-(m + w)] > (m == -(m + w)) + (w == -(m + w)):
yield m, w, -(m + w)
```
4. […] Problem Description Given an array of positive and negative integers, find three that sum to zero. […]

5. Stefan Jaax said

Imho, the proposed solution using hash tables is NOT a valid solution.
To see this, look at the following run on the list [10, -20] (which should return an empty list for all 3 versions of 3sum):

6. Jussi Piitulainen said

Stefan, agreed. That’s precisely why I counted the occurrences in my solution:

```>>> tuple(threesums((10,-20)))
()
>>> tuple(threesums((10,-20,10)))
((10, -20, 10), (10, 10, -20), (-20, 10, 10), (-20, 10, 10), (10, 10, -20), (10, -20, 10))
```

(This is also a hash table solution.)

7. Ronnie said

A c++ implementation of the algorithm.

#include
#include
void three_sum(std::vector input) {
int lo = 1;
int hi = input.size() – 1;
for(int i = 0 ; i < input.size() – 1;) {
if(lo < hi) {
int sum = input[i] + input[hi] + input[lo];
if(sum 0) {
–hi;
} else {
printf(“%d + %d + %d = 0”,input[i],input[lo],input[hi]);
++i;
lo = i+1;
hi = input.size() – 1;
}
} else {
++i;
lo = i+1;
hi = input.size() – 1;
}
}
}