Find four elements that sum to a given value (4Sum problem)

Given an array of integers, find all combination of four elements in the array whose sum is equal to a given value X.

METHOD 1 (Use Sorting)

Algorithm:

Clearly, if we simply test all possible 4-tuples, we'd solve the problem in O(n^4) -- that's the brute-force baseline. Is it possible to do better? What if we pick the tuples in a somewhat smarter way?
First, we invest some time to sort the array, which costs us an initial penalty of O(n log n). Now we execute this algorithm:

for (i=0....n-3) {
 for (j=i+1....n-2) {
  k = j+1  // Start right after i.
  l = n    // Start at the end of the array.

  while (k >= j) {
    // We got a match! All done.
    if (A[i] + A[j] + A[k] +A[l]== 0) return (A[i], A[j], A[k],A[l])

    // We didn't match. Let's try to get a little closer:
    //   If the sum was too big, decrement k.
    //   If the sum was too small, increment j.
    (A[i] + A[j] + A[k]+A[l] > 0) ? l-- : k++
  }
  // When the while-loop finishes, k and l have passed each other and there's
  // no more useful combinations that we can try with this i.
}
}

This algorithm works by placing three pointers, i, j,k and l at various points in the array.We iteratively try to sum the elements at their respective indices, and each time one of the following happens:

The sum is exactly right! We've found the answer.
The sum was too small. Move k closer to the end to select the next biggest number.
The sum was too big. Move l closer to the beginning to select the next smallest number.
For each i &j , the pointers of k and l will gradually get closer to each other. Eventually they will pass each other.

we'll either exhaust the useful possibilities, or we'll find the solution. You can see that this is O(n^3) since we execute the two-outer for loop O(n^2) times and we execute the inner loop O(n) times.

Time Complexity: O(n^3)

Code:

import java.io.*;
import java.util.*;

public class Sum4 {

 static int len=0,sum=0;   
 private static int array[]=new int[len];
 public static void main(String args[]) throws NumberFormatException, IOException  
 {  
  BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
  System.out.println("Enter length of array");
  len =Integer.parseInt(br.readLine()); // take length of array from user  
  
  setArray(Arrays.copyOf(getArray(), getArray().length + len));  // reinitialize array to given length
  
  System.out.println("Enter elements:"); // takes input
  for(int i=0;i<len;i++)
   getArray()[i]=Integer.parseInt(br.readLine());
  
  System.out.println("Enter sum:");
  sum =Integer.parseInt(br.readLine());
  Sum4 s =new Sum4();
  Quicksort q= new Quicksort();
  
  q.sort(0, array.length-1); // to perform sorting
  s.findquadruplets(); // to find Triplet     
 }
 void findquadruplets()
 {   
  for (int i = 0; i < array.length - 3; i++)
     {
   for (int j = i+1; j < array.length - 2; j++)
   {
    int k = j + 1; 
    int l = array.length-1; 
    while (k < l)
    {
     if( array[i] + array[j] + array[k] + array[l] == sum)
     {
      System.out.println("Quadruplets with given sum "+sum+" is (" + array[i]+", "+array[j]+", "+array[k]+", "+array[l]+")");
      break;
     }
     else 
     {                                                                                   
      if (array[i] + array[j] + array[k] + array[l] < sum) 
       k++;
      else 
       l--;
     }
    }
   }
     }
 }
 
 /***************************************************************************
     * functions to access array
  ***************************************************************************/ 
 public static int[] getArray() { //return the array
  return array;
 }
 public static void setArray(int array[]) {  //@param array the array to set
  Sum4.array = array;
 }
}
/***************************************************************************
 * Quicksort
***************************************************************************/ 
class Quicksort
{
 static Sum4 s1 =new Sum4();
 static Quicksort q1= new Quicksort();
 void sort(int low,int high)
 {
  if(high<=low)
   return;
  int j=partition(low, high);
  sort(low,j-1);
  sort(j+1,high);
 }
 int partition(int low,int high)
 {
  int i=low;
  int j=high+1;
  int pivot=Sum4.getArray()[low];
  while(true)
  {
   while(Sum4.getArray()[++i]<pivot)
    if(i== high) break;
   while(pivot<Sum4.getArray()[--j])
    if(j==low) break;
   
   if(i>=j) break;
   q1.exchange(i,j);
  }
  q1.exchange(low,j);
  return j;
 }
 void exchange(int i,int j)
 {
  int temp = Sum4.getArray()[i];
  Sum4.getArray()[i]=Sum4.getArray()[j];
  Sum4.getArray()[j]=temp;
 }
}

/***************************************************************************
OUTPUT: 

Enter length of array
8
Enter elements:
-50
30
140
-100
20
40
-20
984568
Enter sum:
40
Quadruplets with given sum 40 is (-100, -20, 20, 140)
Quadruplets with given sum 40 is (-50, 20, 30, 40)
***************************************************************************/



Or




View on Github

METHOD 2 (Use Hash Map)

.