Open-Source Internship opportunity by OpenGenus for programmers. Apply now.
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.
This problem is also known as "3 Sum problem".
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.
Table of contents:
- Method 1: Naive Approach
- Method 2: Two pointer Technique
- Method 3: Hashing
We will now get started with 3 Sum problem.
Method 1: Naive Approach
In this method, we will find all the possible triplets and compute their sum, till we get the desired sum.
- We are given an array arr of length n and a sum s.
- 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).
- 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.
- 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.
- Sort the given array.
- Use a for loop with counter i to iterate over the whole sorted array.
- During each iteration, take 2 pointers l and r such that l=i+1 and r=arr_size -1.
- 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.
- 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.
- Create a for loop to traverse through the array from start to end (loop counter i).
- Create a Hashmap h that will store values for each iteration.
- An inner for loop will traverse from i+1 to end (loop counter j).
- 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.
- If no such element is present, then insert arr[j] in the Hashmap.
- 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,in this article at OpenGenus, we learned how to find a triplet having a given sum with 3 different methods.
