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 –

- Sort the entire array.
- 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.
- 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.
- If the summation of j
*th*and k*th*elements is less than A[i], then we need to increase the value of the summation of two numbers, by increasing the j*th*pointer. - If the summation of j
*th*and k*th*elements is greater than A[i], then we need to decrease the value of the summation of two numbers, by decreasing the k*th*pointer. - If the sum of the i
*th*and j*th*index is equivalent to the i*th*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.