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.
Programming Praxis 
[…] today’s Programming Praxis exercise, our goal is to find all groups of three numbers in a given list that […]
My Haskell solution (see http://bonsaicode.wordpress.com/2013/06/18/programming-praxis-3sum/ for a version with comments):
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 xsAccepting (-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)[…] Problem Description Given an array of positive and negative integers, find three that sum to zero. […]
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):
http://codepad.org/Sqo8kiCx
Stefan, agreed. That’s precisely why I counted the occurrences in my solution:
(This is also a hash table solution.)
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;
}
}
}