3 Sum problem (Triplets with given Sum)
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.
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..n1]
// 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.