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.

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;
}
Try It

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;
}
Try It


Next > < Prev
Scroll to Top