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

Problem Statement:

Solution

Method 1 - Brute Force

Method 2 - Using Sorting

See also