## 3SUM

### June 18, 2013

We modify the problem statement to return *all* matching triplets, rather than just an arbitrary one of them. Let’s begin with the obvious brute-force algorithm:

`(define (3sum-brute xs)`

(define (x n) (vector-ref xs n))

(let ((len (vector-length xs)))

(list-of (sort < (list (x i) (x j) (x k)))

(i range len)

(j range (+ i 1) len)

(k range (+ j 1) len)

(zero? (+ (x i) (x j) (x k))))))

`> (3sum-brute '#(8 -25 4 10 -10 -7 2 -3))`

((8 -10 2) (10 -7 -3))

We sort the individual triplets just to make them look nice.

There are two ways to improve that, one involving searching and the other involving sorting (isn’t it odd how often that choice arises?). The searching solution enters each array element in a hash table then chooses two items using two nested loops and searches the hash table for the negative of the sum of the two items; we use our new set datatype instead of a hash table, because we don’t need to associate a value with a key:

`(define (3sum-search xs)`

(define (x n) (vector-ref xs n))

(let ((s (make-set 97)) (len (vector-length xs)))

(do ((i 0 (+ i 1))) ((= i len))

(s 'adjoin (x i)))

(list-of (sort < (list (x i) (x j) k))

(i range len)

(j range (+ i 1) len)

(k is (- (+ (x i) (x j))))

(s 'member? k))))

The output of `3sum-search`

is three times as long as it should be, since each triple appears with *k* in each of the three positions. We take a two-pronged approach to the problem; first, the triples are individually sorted (that’s the real reason we sorted them in the brute-force solution), then a `prune`

function uses a set to keep only one copy of each triplet:

`(define (prune xs)`

(let ((s (make-set 97)))

(do ((xs xs (cdr xs))) ((null? xs))

(s 'adjoin (car xs)))

(s 'enlist)))

`> (prune (3sum-search '#(8 -25 4 10 -10 -7 2 -3)))`

((-7 -3 10) (-10 2 8))

The sorting solution first sorts the input array, then tests each item in the array searching for a zero triple in a manner reminiscent of binary search:

`(define (3sum-sort xs)`

(vector-sort! xs cmp)

(let ((len (vector-length xs)) (zs (list)))

(define (x n) (vector-ref xs n))

(do ((i 0 (+ i 1))) ((= i (- len 2)))

(let loop ((lo (+ i 1)) (hi (- len 1)))

(when (< lo hi)

(let ((s (+ (x i) (x lo) (x hi))))

(cond ((negative? s) (loop (+ lo 1) hi))

((positive? s) (loop lo (- hi 1)))

(else (set! zs (cons (sort < (list (x i) (x lo) (x hi))) zs))))))))

zs))

`> (3sum-sort '#(8 -25 4 10 -10 -7 2 -3))`

((-7 -3 10) (-10 2 8))

We used list comprehensions and the Bentley-McIlroy vector sort from the Standard Prelude. You can run the program at http://programmingpraxis.codepad.org/zW0EmC9m.

[…] 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):

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.

[…] 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;

}

}

}