## Friday, January 17, 2014

### 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