3 sum problem

Problem Statement:

Problem

Given a set S of n integers find all possible subsets(a,b,c) such that a + b + c = 0.

 Making more generic:

 Given a set S of n integers find all possible subsets(a,b,c) such that a + b + c = T.

Solution

Brute force approach is of O(n^3) but we can solve it in O(n^2) by using the approach in 2 sum problem approach.

Method 1 - Brute Force

A simple method is to generate all possible triplets and compare the sum of every triplet to 0. 

Code (Java)

boolean threeSumBrute(int arr[], int sum=0)
{  
  int n = arr.length;
    // Fix the first element as A[i]
    for (int i = 0; i < n-2; i++)
    {
       // Fix the second element as A[j]
       for (int j = i+1; j < n-1; j++)
       {
           // Now look for the third number
           for (int k = j+1; k < n; k++)
           {
               if (arr[i] + arr[j] + arr[k] == sum)
               {
                 System.out.printf("Triplet is %d, %d, %d", arr[i], arr[j], arr[k]);
                 return true;
               }
           }
       }
    }
 
    // If we reach here, then no triplet was found
    return false;
}
// calling
int arr[] = {1, -4, 45, -6, 10, 8};
boolean ifExist = threeSumBrute(arr)
//Output = -4, -6, 10
 

Time complexity - O(n^3) 

Method 2 - Using Sorting

First sort the array(Order O(nlogn)), than finding a, b, c pairs is equal to finding=> For every element a in the array, if there exists a pair with sum equal to -a. As explained in 2 sum problem, we can get the pair with sum -a in O(n) and we have to repeat this exercise n times so order of complexity will be O(n^2).

Code (Java)

boolean threeSumSorting(int A[], int sum)
{
    int l, r;
    int n = A.length;
    Arrays.sort(A);
 
    // Now fix the first element one by one and find the
    //   other two elements 
    for (int i = 0; i < n - 2; i++)
    {
 
        // To find the other two elements, start two index variables
        // from two corners of the array and move them toward each
        // other
        l = i + 1; // index of the first element in the remaining elements
        r = n-1; // index of the last element
        while (l < r)
        {
            if( A[i] + A[l] + A[r] == sum)
            {
                System.out.printf("Triplet is %d, %d, %d", A[i], A[l], A[r]);
                return true;
            }
            else if (A[i] + A[l] + A[r] < sum)
                l++;
            else // A[i] + A[l] + A[r] > sum
                r--;
        }
    }
 
    // If we reach here, then no triplet was found
    return false;
}

Time complexity : O(n^2)

Here is the gist for this problem : https://gist.github.com/kinshuk4/eed182627f6c7cf5a7e94282801569a6
Reference

• http://en.wikipedia.org/wiki/3SUM 
• http://leetcode.com/2010/04/finding-all-unique-triplets-that-sums.html 
• http://tianrunhe.wordpress.com/2012/07/07/finding-all-unique-triplets-that-sums-to-zero-3sum/