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.
Programming Praxis 
[…] 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):
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]Solution in Kawa Scheme:
4-SUM on Codepad
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[…] 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; }An inefficient solution in Common Lisp.
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)))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:
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 Noneimport 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:
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))[…] 4SUM […]