Home » Technical Interview Questions » Array Interview Questions » Find Triplet in Array With a Given Sum

# Find Triplet in Array With a Given Sum

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. If there is no such combination then print -1.

## Example

Input

N=5, X=15

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

Output

10, 2, 3

## Approach 1

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

### Algorithm

1. First sort the input array
2. Fix the first element as arr[i], where i ranges from 0 to N-2.
3. After Fixing the first element, fix the second element as arr[j], where j ranges from  i+1 to N-1.
4. After fixing the second element, fix the third element as arr[k], where k ranges from j+1 to N.
5. Find the sum, arr[i] + arr[j] + arr[k].
6. If the Triplet sum is equal to the value X, print the three elements else print -1.

### C++ Program for Find Triplet in Array With a Given Sum

```#include <bits/stdc++.h>
using namespace std;
int main()
{
int N,X;//size of the array
cin>>N>>X;
int arr[N];
for(int i=0;i<N;i++)
{
cin>>arr[i];
}
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<<-1<<endl;
return 0;
}```
```5 15
10 4 2 3 5```
`10  2  3`

## Approach 2

Algorithm

1. First sort the input array
2. Fix the first element as arr[i], where i ranges from 0 to N-2.
3. 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 a sorted array.
4. 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 for Find Triplet in Array With a Given Sum

```#include <bits/stdc++.h>
using namespace std;
int main()
{
int N,X;//size of the array
cin>>N>>X;
int arr[N];
for(int i=0;i<N;i++)
{
cin>>arr[i];
}
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<<-1<<endl;
return 0;
}```
```5 15
1 4 2 3 5```
`-1`

### Complexity Analysis for Find Triplet in Array With a Given Sum

#### Time Complexity

O(n*n*n) where n is the number of elements present in the array. Here we Ron three for loop and check for every possible triplet.

READ  Peak Index in a Mountain Array

#### Space Complexity

O(1) because we don’t use any auxiliary space here.

References

 Array Interview Questions Graph Interview Questions LinkedList Interview Questions String Interview Questions Tree Interview Questions