Find all triplets such that sum of two equals to third element

We are given an array of n distinct integers and we have to find all triplets (3 elements), such that the sum of two elements equals the third element.

Input : {7, 34, 3, 9, 12, 52, 21, 23, 4}
Output : (3,9,12)
         (3,4,7)
         (3,9,12)

The naive approach of solving this problem would be to run a nested loop and compare the sum of every two elements with the third element and see if triplet exits. But this will have O(N³) run time complexity which is very poor.

Following is an efficient way of solving this problem in O(N²) time –

1. Sort the entire array.
2. Start from the last element i(initially i=n-1), and now move back to find the other two elements with the sum equivalent to the third element.
3. Take two pointers j(from the front) and k(initially i-1) to find the smallest of the two numbers and from i-1 to find the largest of the two remaining numbers.
4. If the summation of jth and kth elements is less than A[i], then we need to increase the value of the summation of two numbers, by increasing the jth pointer.
5. If the summation of jth and kth elements is greater than A[i], then we need to decrease the value of the summation of two numbers, by decreasing the kth pointer.
6. If the sum of the ith and jth index is equivalent to the ith element.

Algorithm

find_triplet(arr, n)
{
    sort(arr)
    for(i=n-1; i>=0; i--)
    {
        j=0; 
        k=i-1;
        while(j<k)
        {
            if(arr[j] + arr[k] == arr[i])
                print(arr[j], arr[k], arr[i])
            else if(arr[j] + arr[k] > arr[i])
                k-=1;
            else
                j+=1;
        }
    }
}

Implementation of the above algorithm

//CPP program to implement the above algorithm
 
#include <bits/stdc++.h> 
using namespace std; 
   
int find_triplet(int* arr, int n) 
{ 
    bool trip_exits = false;
    //sort the array in ascending order
    sort(arr, arr+n); 
    for(int i=n-1; i>=0; i--) 
    { 
        int j=0; 
        int k=i-1; 
        
        while(j<k) 
        { 
            if(arr[j] + arr[k] == arr[i]){
                cout<<"("<<arr[j] <<","<<arr[k]<<","<< arr[i]<<")" << endl;
                trip_exits = true;
                break;
            }  
            else if(arr[j] + arr[k] > arr[i]) 
                k-=1; 
            
            else 
                j+=1; 
        } 
    } 

    if(!trip_exits)
        cout<<"Triplet pairs doesnt exits";

    return 0;
}

int main()
{
    int arr[] = {7, 34, 3, 9, 12, 52, 21, 23, 4};
    int n = sizeof(arr)/sizeof(arr[0]);

    find_triplet(arr, n);

    return 0;
}

Output

(9,12,21)
(3,9,12)
(3,4,7)

Time Complexity

The run time complexity of the above algorithm is O(N²).
The sorting algorithm will take O(NlogN) time. Now there is also, a nested loop, which will give time complexity of O(N²). Hence overall complexity will be O(NlogN + N²) ≈ O(N²)

This is how we will solve the problem that requires us to find all triplets, such that the sum of two elements equals the third element.