×

Search anything:

3 Sum problem (Triplets with given Sum)

Algorithms hash map Interview Problems on Array

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.

1. Method 1: Naive Approach
2. Method 2: Two pointer Technique
3. 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.

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,in this article at OpenGenus, we learned how to find a triplet having a given sum with 3 different methods.

Amruta U. Koshe

Amruta is a Computer Science B. Tech student at A. P. Shah Institute of Technology, Thane (2018 to 2022) and has been an Algorithm and Data Structure Developer, Intern at OPENGENUS.

3 Sum problem (Triplets with given Sum)