## 4SUM

### August 14, 2012

We have today another exercise from our inexhaustible stock of interview questions:

Given an array of integers, output a list of four integers that sum to zero (the same input integer can be used multiple times), or indicate that no such set of four integers exists. For example, given the array (2 3 1 0 -4 -1), the set of four integers (3 1 0 -4) sums to zero, as does the set (0 0 0 0).

Your task is to write a program that solves the interview question. 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.

About these ads

Pages: 1 2

### 14 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 [...]

3. 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]
```
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 [...]

6. madscifi said

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);
read(bil[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();
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;
}

}

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