# Find Triplet in Array With a Given Sum

Difficulty Level Medium
Frequently asked in Accolite Adobe Amazon Apple Bloomberg ByteDance Cisco Citadel Citrix DoorDash eBay Facebook Goldman Sachs Google Hulu IBM Infosys Mathworks Microsoft Morgan Stanley Oracle PayPal Qualtrics Samsung ServiceNow Splunk Square Tencent Tesla Uber Visa VMware Walmart Labs Yahoo Zoho
Akamai Array CarWale Groupon Postmates Works Applications

## Problem Statement

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.

### Implementation

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

#### Java Program for Find Triplet in Array With a Given Sum

```import java.util.Scanner;
class sum
{
public static void main(String[] args)
{
Scanner sr = new Scanner(System.in);
int n = sr.nextInt();
int x = sr.nextInt();
int a[] = new int[n];
for(int i=0;i<n;i++)
{
a[i] = sr.nextInt();
}
int temp=0;
for(int i=0;i<n;i++)
{
for(int j=i+1;j<n;j++)
{
for(int k=j+1;k<n;k++)
{
if( a[i] + a[j] + a[k] == x)
{
System.out.println(a[i]+"  "+a[j]+"  "+a[k]);
i=n;j=n;k=n;
temp=1;
}
}
}
}
if(temp==0)
System.out.println(-1);
}
}```
```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.

### Implementation

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

#### Java Program for Find Triplet in Array With a Given Sum

```import java.util.Arrays;
import java.util.Scanner;
class sum
{
public static void main(String[] args)
{
Scanner sr = new Scanner(System.in);
int n = sr.nextInt();
int x = sr.nextInt();
int a[] = new int[n];
for(int i=0;i<n;i++)
{
a[i] = sr.nextInt();
}
Arrays.sort(a); //sort the array in ascending order
int computed_sum;//sum computed at each step
int temp=0;
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 = a[i] + a[j] + a[k]; // add the elements at the given indices
if(computed_sum == x)
{
System.out.println(a[i]+"  "+a[j]+"  "+a[k]);
j=k;
temp=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--;
}
}
if(temp==0)
System.out.println(-1);
}
}```
```5 15
1 4 2 3 5```
`-1`

### Complexity Analysis

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