Triplet that sum to a given value.

Method

Time Complexity: O(N^2)

1. First sort the input array
2. Fix the first element as arr[i], where i ranges from 0 to N-2

a. After fixing the first element, for finding the next two elements, take two pointer like variables ( j = i+1, k= N-1) and traverse the algorithm for finding the sum in sorted array.

b. while j is less than k Add the elements at the given indexes ie, arr[i] + arr[j] + arr[k] if Triplet sum is equal to the value X, print the three elements else if Triplet sum is less than the value X, then increase the j value else decrease the value of k.

code :-

[code language=”cpp”]
#include <bits/stdc++.h>
using namespace std;

int main()
{
int arr[] = {18, 17, 8, 10, 19, 11, 12, 3, 4, 1, 6, 9}; //array
int N = sizeof(arr)/sizeof(arr[0]);//size of array

int X;
cin>> X; //number to which a triplet should sum to

sort(arr,arr+N); //sort the array in ascending order
int computed_sum;//sum computed at each step

for(int i = 0; i < N – 2; i++) // fix one element and search for other two elements in linear time
{
int j = i+1 , k = N-1; // jth index starts from the next element of selected and k always starts at the ending index

while(j < k)
{
computed_sum = arr[i] + arr[j] + arr[k]; // add the elements at the given indices

if(computed_sum == X)
{
cout << arr[i] <<" "<<arr[j]<<" "<<arr[k];
return 1;
}
else if(computed_sum < X) // means we need to increase some element but as i is fixed and k is already higher than i and j. We increment jth index
j++;

else if(computed_sum > X)//means we need to decrease some element but as i is fixed and j is already smaller than kth index element , we decrement k
k–;
}
}

cout<<"No Such triplet exists\n";
return 0;
}
[/code]