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.

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. 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;
    }
    
  6. 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)))
    
    
  7. 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.

  8. [...] 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)))) [...]

  9. 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
    
  10. 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;
    }

    }

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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 621 other followers

%d bloggers like this: