## 4SUM

### August 14, 2012

There are several solutions to this problem. One generates all combinations using four nested loops, summing each; it has time complexity O(n4). Another sets up three nested loops, sums each triple, and checks if the negative of the triple exists in the array; that has time complexity O(n3).

The best solution is O(n2), and is based on rewriting the sum a + b + c + d = 0 as a + b = -(c + d). Use two nested loops to store all n2 sums a + b in some sort of dictionary (hash table, balanced tree) and with the components a and b, then use two nested loops to compute all sums c + d and check if the negative of the sum exists in the dictionary. We use an avl tree:

```(define (4sum target xs)   (call-with-current-continuation     (lambda (return)       (let ((d (make-dict <)))         (do ((as xs (cdr as))) ((null? as))           (do ((bs xs (cdr bs))) ((null? bs))             (set! d               (d 'insert                 (+ (car as) (car bs))                 (list (car as) (car bs))))))         (do ((cs xs (cdr cs))) ((null? cs))           (do ((ds xs (cdr ds))) ((null? ds))             (awhen (d 'lookup (- target (car cs) (car ds)))               (return (cons* (car cs) (car ds) (cdr it))))))         (return #f)))))```

We generalized a little bit, allowing any target, not just 0, because it’s just as easy, and more useful. This is a kind of meet-in-the-middle algorithm, because the solution works from both ends.

There are two bits of Scheme trickiness here. The first uses `call-with-current-continuation` to define a function `return` that stops execution and returns a value in the middle of the function. The second is Paul Graham’s anaphoric when: `awhen` executes the dictionary lookup, and if it returns some non-`#f` value binds it to the variable `it`. Here’s an example:

```> (4sum 0 '(2 3 1 0 -4 -1)) (2 2 -4 0) > (4sum 0 '(1 2 3 4 5 6)) #f > (4sum 13 '(1 2 3 4 5 6)) (1 1 6 5)```

We used `cons*`, `make-dict`, `define-macro`, `aif` and `awhen` from the Standard Prelude. You can run the program at http://programmingpraxis.codepad.org/rPIIfCh4.

Pages: 1 2

### 15 Responses to “4SUM”

1. uberlazy said
```(defn- sum4* [coll so-far]
(cond (empty? coll) nil
(= (count so-far) 4)
(if (= 0 (reduce + so-far))
[so-far]
nil)
:else
(concat (sum4* (rest coll) so-far)
(sum4* coll (cons (first coll) so-far)))))

(defn sum4 [coll]
(sum4* coll []))
```
2. […] today’s Programming Praxis exercise, our goal is to find four integers in a given list that sum up to a […]

```import qualified Data.IntMap as I

sum4 :: Int -> [Int] -> [[Int]]
sum4 n xs = take 1 [p1++p2 | (s, p1) <- I.assocs pairs
, p2 <- maybe [] return \$ I.lookup (n-s) pairs]
where pairs = I.fromList [(a+b, [a,b]) | a <- xs, b <- xs]
```
4. Mike said

Python

```from itertools import combinations_with_replacement
def sumof4(nums, tgt=0):
rems = {}
for c, d in combinations_with_replacement(nums, r=2):
s = c + d
if s in rems:
a, b = rems[s]
return a, b, c, d

else:
rems[tgt - s] = c, d

return None
```
5. […] Pages: 1 2 […]

Requires -std=c++0x option when compiled with g++.

```#include <iostream>
#include <map>
#include <list>

template<class IT, class VT = typename std::iterator_traits<IT>::value_type>
std::list<VT> sum4( IT a, IT aend )
{
std::map< VT, std::pair<VT, VT> > amap;
for( IT i = a; i != aend; ++i )
{
for( IT j = i; j != aend; ++j )
{
amap[ *i + *j ] = std::make_pair( *i, *j );
auto iter = amap.find( -(*i + *j) );
if( iter != amap.end() )
{
return std::list<VT> { *i, *j, iter->second.first, iter->second.second };
}
}
}
return std::list<VT>();
}

int main( int argc, char**argv )
{
std::list<int> a = { 2, 3, 1, 0, -4, -1 };
auto r = sum4( std::begin(a), std::end(a) );
if( !r.empty() )
{
for( auto i : r ) std::cout << i << " ";
std::cout << std::endl;
}
else
{
std::cout << "no items 4 sum to zero" << std::endl;
}
return 0;
}
```
7. Another Clojure solution:

```
(ns programming_praxis.core
(:use clojure.contrib.combinatorics))

(defn collect-if-solution
[pair sum sums solutions]
(if (contains? sums (- sum))
(conj solutions (sort (concat pair (get sums (- sum)))))
solutions))

(defn four-sum
[nums]
(loop [sums {} pairs (selections nums 2) solutions ()]
(if (empty? pairs)
(distinct solutions)
(let [pair (first pairs)
sum  (apply + pair)]
(recur
(assoc sums sum pair)
(rest pairs)
(collect-if-solution pair sum sums solutions))))))

(println (four-sum '(2 3 1 0 -4 1)))

```
8. Jarvis said

program foursum;

var bil:array [1..1000] of integer;
test:array [1..4] of integer;
i,j,k,l:integer;

procedure testing;
var cc,hasil:integer;
begin
hasil:=0;
for cc:= 1 to 4 do hasil:=hasil+test[cc];
if hasil = 0 then begin
for cc:= 1 to 4 do write(test[cc],’ ‘);
writeln;
end;
end;

procedure permut(xx:integer);
var hasil,bb:integer;
begin
if xx = 4 then begin
for bb:= 1 to i do begin
test[4]:= bil[bb];
testing;
end;
end
else
begin
for bb:= 1 to i do begin
test[xx]:=bil[bb];
permut(xx+1);
end;
end;
end;

begin
i := 0;
while not eof do begin
inc(i);
end;

permut(1);
end.

9. […] One more from Programming Praxis, this time we’re dealing with summing combinations of a sequence. More formally, given a secquence S, either choose four elements s1 through s4 from S such that s1+s2+s3+s4 = 0 or verify that it isn’t possible. This immediately makes me about working through possible solutions until we find one and then bailing out, ergo call/cc: (define (4sum ls) (call/cc (lambda (exit) (for-each (lambda (i) (for-each (lambda (j) (for-each (lambda (k) (for-each (lambda (l) (when (= 0 (+ i j l k)) (exit (list i j k l)))) ls)) ls)) ls)) ls) (exit #f)))) […]

10. cosmin said

Another Python solution:

```def zeroSum(numbers):
dictionary = {}
for a in numbers:
for b in numbers:
dictionary[a+b] = [a, b]
if -(a+b) in dictionary:
[c, d] = dictionary[-(a+b)]
return [a, b, c, d]
return None
```
11. Ankit Thakur said

import java.io.*;
import java.util.ArrayList;
public class combination {
ArrayList values=new ArrayList();
public void problem1()
{
try
{
ArrayList array=new ArrayList();
System.out.println(“Input the size of array”);
for(int count=1;count<=number;count++)
{
System.out.println("Input the elements of array");
}
for(int count1=0;count1<array.size();count1++)
{
for(int count2=0;count2<array.size();count2++)
{
for(int count3=0;count3<array.size();count3++)
{
for(int count4=0;count4<array.size();count4++)
{
if(sum(array.get(count1),array.get(count2),array.get(count3),array.get(count4)))
{
if(check(array.get(count1),array.get(count2),array.get(count3),array.get(count4)))
{
}
}
}
}
}
}
if(values.size()==0)
{
System.out.println("No elements Present");
}
else
System.out.println(values);
}
catch(IOException ioe)
{
ioe.printStackTrace();
}
}
public boolean sum(int num1,int num2,int num3,int num4)
{
if(num1+num2+num3+num4==0)
return true;
else
return false;
}
public boolean check(int value1,int value2,int value3,int value4)
{
ArrayList number_present=new ArrayList();
for(String used_number:values)
{

ArrayList number_present_copy=new ArrayList(number_present);
String number[]=used_number.split(“,”);
for(int count=0;count<number.length;count++) //each number counter
{
for(int i=0;i<number_present_copy.size();i++)
{
if(number[count].equals(Integer.toString(number_present_copy.get(i))))
{
number_present_copy.remove(i);
break;
}
}
}
if(number_present_copy.size()==0)
return false;

}
return true;
}

}

12. David said

Lacking any insight, in Python:

```    import sys
sys.setrecursionlimit(10000)

def divide(v1):
x = []
y = []
zed = False
for i in v1:
if i < 0:
y.append(i)
elif i > 0:
x.append(i)
elif i == 0:
zed = True
x.sort()
x.reverse()
y.sort()
return x, y, zed

def walk(x, y, l):
if len(l) == 4 and sum(l) == 0:
return l
elif len(l) == 4:
return False
elif len(l) == 3 and sum(l) == 0:
return False

if sum(l) > 0:
for n in y:
result = walk(x, y, l + [n,])
if result and sum(result) == 0:
return result
if sum(l) < 0:
for n in x:
result = walk(x, y, l + [n,])
if result and sum(result) == 0:
return result
return False

def process(v1):
x, y, z = divide(v1)
if z:
return [0,]*4
if not x or not y:
return []
y *= 4
x *= 4
for n in xrange(len(x)):
result = walk(x, y, [x[n]])
if result and sum(result) == 0:
return result
for n in xrange(len(y)):
result = walk(x, y, [y[n]])
if result and sum(result) == 0:
return result

print process((2, 3, 1, -4, -1))
```