# Find triplet in array with a given sum

0
658

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

Previous articleFind element using binary search in sorted array
If you have come this far, it means that you liked what you are reading. I am a software developer (graduated from BITS Pilani). I love writing technical articles on programming and data structures.