Triplets with given Sum

Binary Tree Problems books

Get FREE domain for 1st year and build your brand new site

Given an array, we need to find if there is a triplet in the array whose sum is equal to a given value. If such a triplet is present, we need to print it and return true. Else, return false.

  • Example -
    Input: arr = [3,4,12,6,2,9] , sum = 24
    Output: 3 , 12 , 9
    Explanation: The triplet(3,9,12) give us a sum of 24.

Method 1- Naive Approach

In this method, we will find all the possible triplets and compute their sum, till we get the desired sum.

  1. We are given an array arr of length n and a sum s.
  2. We will create 3 nested for loops to find different combinations of triplets. The first loop will traverse from start to end (loop counter i), the second loop will run from i+1 to end (loop counter j) and the third loop from j+1 to end (loop counter k).
  3. In the innermost loop, we will calculate the sum of ith, jth and kth element. If the sum matches the desired sum, print the 3 values and return true.
  4. If we reach the end of the loops without any match, return false.

Code -

#include <bits/stdc++.h> 
using namespace std; 

// returns true if there is triplet with sum equal 
// to 'sum' present in arr[] and prints the triplet 
bool triplet(int arr[], int arr_size, int sum) 
{ 
	int l, r; 
 
    //loop counter i for first element
	for (int i = 0; i < arr_size - 2; i++) 
	{ 
 
        //loop counter j for second element
		for (int j = i + 1; j < arr_size - 1; j++) 
		{ 

 
            //loop counter k for third element
			for (int k = j + 1; k < arr_size; k++) 
			{ 
				if (arr[i] + arr[j] + arr[k] == sum) 
				{ 
					cout << "Triplet is " << arr[i] << 
						", " << arr[j] << ", " << arr[k]; 
					return true; 
				} 
			} 
		} 
	} 

	//returns false if no such triplet is found 
	return false; 
} 

/* Driver code */
int main() 
{ 
	int arr[] = { 1, 4, 2, 6, 10, 8}; 
	int sum = 9; 
	int arr_size = sizeof(arr) / sizeof(arr[0]); 
	triplet(arr, arr_size, sum); 
	return 0; 
} 

Output -

Triplet is 1, 2, 6

Complexity -

  • Time Complexity - O(n^3) as there are 3 nested loops.
  • Space Complexity - O(1) as no extra space is required.

Method 2 - Two-pointer Technique

In this method, we will use 2 pointers inside a for loop to keep track of triplet combinations. However, we would need to sort the array first as we need to compare the elements.

  1. Sort the given array.
  2. Use a for loop with counter i to iterate over the whole sorted array.
  3. During each iteration, take 2 pointers l and r such that l=i+1 and r=arr_size -1.
  4. Use another loop while l<r, to calculate the sum i.e arr[i] + arr[l] + arr[r].
  • If the sum is greater than the desired sum, decrement r by 1.
  • If the sum is smaller than the desired sum, increment l by 1.
  • If the sum is equal to the desired sum, print the triplets and return true.
  1. If the whole loop is iterated, then we will return false as we did not find any triplet that satisfies the condition.

Code -

#include <bits/stdc++.h> 
using namespace std; 
  
// returns true if there is triplet with sum equal 
// to 'sum' present in arr[] and prints the triplet 
bool triplet(int arr[], int arr_size, int sum) 
{ 
    int l, r; 
  
    // Sort the elements 
    sort(arr, arr + arr_size); 
  
    /* Now fix the first element one by one and find the 
       other two elements */
    for (int i = 0; i < arr_size - 2; i++) { 
  
        // To find the other two elements, start two index 
        // variables from two corners of the array and move 
        // them toward each other 
        
        l = i + 1; // index of the first element in the 
        // remaining elements 
  
        r = arr_size - 1; // index of the last element 
        while (l < r) { 
            if (arr[i] + arr[l] + arr[r] == sum) { 
                printf("Triplet is %d, %d, %d", arr[i], 
                       arr[l], arr[r]); 
                return true; 
            } 
            else if (arr[i] + arr[l] + arr[r] < sum) 
                l++; 
            else // A[i] + A[l] + A[r] > sum 
                r--; 
        } 
    } 
  
    // If we reach here, then no triplet was found 
    return false; 
} 
  
// Driver code
int main() 
{ 
    int arr[] = { 1, 4, 45, 6, 10, 8 }; 
    int sum = 22; 
    int arr_size = sizeof(arr) / sizeof(arr[0]); 
  
    triplet(arr, arr_size, sum); 
  
    return 0; 
} 

Output -

Triplet is 4, 8, 10

Workflow -

Let's understand this problem with an example.

  • Input : arr = [1, 4, 45, 6, 10, 8] , sum = 22

First, we'll sort the given array.
Hence, arr = [1, 4, 6, 8, 10, 45]

Then we will iterate through the loops :

  • For i =0, l =1 and r =5
    l < r is true
    arr[i] + arr[l] + arr[r] = 1 + 4 + 45 = 50 > 22
    i.e. r-- = 4

Similarly, we will execute the while loop till l< r

  • For i =1, l=3, and r=4, we'll get arr[i] + arr[l] + arr[r] = 22
    Hence, it will print the triplet and return true.

Complexity -

  • Time Complexity - O(n^2) as there are 2 nested loops.
  • Space Complexity - O(1) as no extra space is required.

Method 3 - Hashing

We need to use extra space in this method, but it is a relatively simpler method. We use 2 loops to traverse from start to end and a hashmap that will store some elements.

  1. Create a for loop to traverse through the array from start to end (loop counter i).
  2. Create a Hashmap h that will store values for each iteration.
  3. An inner for loop will traverse from i+1 to end (loop counter j).
  4. If there is an element in the Hashmap which is equal to sum - arr[i] - arr[j], then print the triplet (arr[i] , arr[j] , sum - arr[i] - arr[j]) and return true.
  5. If no such element is present, then insert arr[j] in the Hashmap.
  6. Return false if the loops are executed as it means there is no triplet satisfying the condition.

Code -

#include <bits/stdc++.h> 
using namespace std; 
  
// returns true if there is triplet with sum equal 
// to 'sum' present in A[]. Also, prints the triplet 
bool triplet(int arr[], int arr_size, int sum) 
{ 
    // Fix the first element as A[i] 
    for (int i = 0; i < arr_size - 2; i++)  
    { 
  
        // Find pair in subarray A[i+1..n-1] 
        // with sum equal to sum - A[i] 
        unordered_set<int> h; 
        int curr_sum = sum - arr[i]; 
        for (int j = i + 1; j < arr_size; j++)  
        { 
            if (h.find(curr_sum - arr[j]) != h.end())  
            { 
                printf("Triplet is %d, %d, %d", arr[i], 
                      arr[j], curr_sum - arr[j]); 
                return true; 
            } 
            h.insert(arr[j]); 
        } 
    } 
  
    // If we reach here, then no triplet was found 
    return false; 
} 
  
/* Driver program to test above function */
int main() 
{ 
    int arr[] = { 1, 8, 5, 6, 10, 3 }; 
    int sum = 9; 
    int arr_size = sizeof(arr) / sizeof(arr[0]); 
  
    triplet(arr, arr_size, sum); 
  
    return 0; 
} 

Output -

Triplet is 1, 3, 5

Workflow -

Let us understand this solution with an example

  • Input: arr=[ 1, 8, 5, 3, 10, 6 ], sum = 9

We will iterate through the array with nested for loops.

-For i=0:
h = [] (The hashmap is empty)
curr_sum = sum - arr[i] = 8

  • j = 1
    curr_sum - arr[j] i.e 0 isn't found in the hashmap
    therefore, we will store arr[j] in h
    h = [8]

  • j = 2
    curr_sum - arr[j] i.e 3 isn't found in the hashmap, so we will add 5 in h
    h = [8,5]

  • j=3
    curr_sum - arr[j] = 5.
    5 is present in the hashmap.

Hence, for i =0, we found a pair of value whose sum is 8 (where sum - arr[i] = 8)

Therfore, we will print the triplet as (arr[0], arr[j] , curr_sum - arr[j]) and return true.

Complexity -

  • Time Complexity - O(n^2) as there are 2 nested loops.
  • Space Complexity - O(n) as we use a hashmap to store elements.

Conclusion -

Hence, we learned how to find a triplet having a given sum with 3 different methods.