## 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*(*n*^{4}). 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*(*n*^{3}).

The best solution is *O*(*n*^{2}), and is based on rewriting the sum *a* + *b* + *c* + *d* = 0 as *a* + *b* = -(*c* + *d*). Use two nested loops to store all *n*^{2} 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.

[…] today’s Programming Praxis exercise, our goal is to find four integers in a given list that sum up to a […]

My Haskell solution (see http://bonsaicode.wordpress.com/2012/08/14/programming-praxis-4sum/ for a version with comments):

Solution in Kawa Scheme:

4-SUM on Codepad

Python

[…] Pages: 1 2 […]

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

An inefficient solution in Common Lisp.

Another Clojure solution:

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);

read(bil[i]);

end;

permut(1);

end.

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

Another Python solution:

import java.io.*;

import java.util.ArrayList;

public class combination {

ArrayList values=new ArrayList();

public void problem1()

{

try

{

ArrayList array=new ArrayList();

BufferedReader br=new BufferedReader(new InputStreamReader(System.in));

System.out.println(“Input the size of array”);

int number=(Integer.parseInt(br.readLine()));

for(int count=1;count<=number;count++)

{

System.out.println("Input the elements of array");

int value=Integer.parseInt(br.readLine());

array.add(value);

}

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)))

{

values.add(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();

number_present.add(value1);

number_present.add(value2);

number_present.add(value3);

number_present.add(value4);

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;

}

}

Lacking any insight, in Python:

[…] 4SUM […]