## Given an array of integers, find the combination of three elements in the array whose sum is equal to a given value X.

Here we will print the first combination that we get.

**For example**

**Input :**

arr[]={10, 4, 2, 3, 5} and X = 15

**Output :Â **

10, 2, 3

## Algorithm 1

**Time complexity : O(n^3)**

Generating all the triplets and comparing the sum to the given value. Below algorithm contains three loops.

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, fix the second element as arr[j], where j is ranges fromÂ i+1 to N-1

b. After fixing the second element, fix the third element as arr[k], where k ranges from j+1 to N

Find the sum, arr[i] + arr[j] + arr[k]

if the Triplet sum is equal to the value X, print the three elements

## C++ Program

```
#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
for(int i = 0; i < N;i++)
for(int j = i+1; j <N; j++)
for(int k = j+1 ; k <N;k++)
if( arr[i] + arr[j] + arr[k] == X)
{
cout << arr[i] <<" "<<arr[j]<<" "<<arr[k];
return 1;
}
cout<<"No Such triplet exists\n";
return 0;
}
```

## Algorithm 2

**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.

## C++ Program

```
#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;
}
```