Given an array of distinct elements. The task is to find triplets in array whose sum is equal to a given number. Examples: Input: arr[] = {0, -1, 2, -3, 1}
sum = -2
Output: 0 -3 1
-1 2 -3
If we calculate the sum of the output,
0 + (-3) + 1 = -2
(-1) + 2 + (-3) = -2
Input: arr[] = {1, -2, 1, 0, 5}
sum = 0
Output: 1 -2 1
If we calculate the sum of the output,
1 + (-2) + 1 = 0Method 1: Brute Force. Approach: The brute force approach in these type of questions aim to check all possible triplets present in the array. The triplet with sum=Target sum will be the answer. Now the question that arises is how should one check all possible
triplets. To check all possible duplets fix a pointer on one element and for every such element traverse the array and check the sum. This will be the sum of all possible duplets. Likewise for checking all possible triplets one can fix two-pointers and move the third pointer over the array and as soon as it reaches the end of array increment the second pointer and again repeat the same. Algorithm:
- Take three pointers i, j, k.
- Initialize i with zero and start a nested loop for i.
- Initialize j with (i+1) and start a nested loop for j.
- Initialize k with (j+1) and start a loop for k.
- If Target == arr[i] + arr[j] + arr[k] break the loop and print
values of arr[i], arr[j], arr[k].
- Else keep incrementing k till it is equal to last index.
- Goto step 2 and increment j and for every value of j run the inner loop of k.
- If j is equal to 2nd last index Goto step 1 and increment the value of i till 3rd last index and again
continue the whole process till the value of i is equal to the last index.
Implementation: C++#include <bits/stdc++.h>
using namespace std;
void findTriplets(int arr[], int n, int sum)
{
for (int i = 0; i < n - 2; i++) {
for (int j = i + 1; j < n - 1; j++) {
for (int k = j + 1; k < n; k++) {
if
(arr[i] + arr[j] + arr[k] == sum) {
cout << arr[i] << " "
<< arr[j] << " "
<< arr[k] << endl;
}
}
}
}
}
int main()
{
int arr[] = { 0, -1, 2, -3, 1 };
int n = sizeof(arr) / sizeof(arr[0]);
findTriplets(arr, n, -2);
return 0;
}
Javaimport
java.io.*;
class GFG {
static void findTriplets(int arr[],
int n, int sum)
{
for (int i = 0;
i < n - 2; i++) {
for (int j = i + 1;
j < n - 1; j++) {
for (int k = j + 1;
k < n; k++) {
if (arr[i] + arr[j] + arr[k] == sum) {
System.out.println(
arr[i] + " " + arr[j]
+ " " + arr[k]);
}
}
}
}
}
public static void main(String[] args)
{
int arr[] = { 0, -1, 2, -3, 1 };
int n = arr.length;
findTriplets(arr, n, -2);
}
}
Python3def findTriplets(arr, n, sum):
for i in range(0, n - 2):
for j in range(i + 1, n - 1):
for k in range(j + 1, n):
if (arr[i] + arr[j] +
arr[k] == sum):
print(arr[i], " ",
arr[j], " ",
arr[k], sep = "")
arr = [ 0, -1, 2, -3, 1 ]
n = len(arr)
findTriplets(arr, n, -2)
C#using System;
class GFG {
static void findTriplets(int[] arr,
int n, int sum)
{
for (int i = 0;
i < n - 2; i++) {
for (int j = i + 1;
j < n - 1; j++) {
for (int k = j + 1;
k < n; k++) {
if (arr[i] + arr[j] + arr[k] == sum) {
Console.WriteLine(
arr[i] + " " + arr[j]
+ " " + arr[k]);
}
}
}
}
}
static public
void Main()
{
int[] arr = { 0, -1, 2, -3, 1 };
int n = arr.Length;
findTriplets(arr, n, -2);
}
}
PHP<?php
function findTriplets($arr, $n, $sum)
{
for ($i = 0; $i < $n - 2; $i++)
{
for ($j
= $i + 1; $j < $n - 1; $j++)
{
for ($k = $j + 1; $k < $n; $k++)
{
if ($arr[$i] + $arr[$j] +
$arr[$k] == $sum)
{
echo
$arr[$i], " ",
$arr[$j], " ",
$arr[$k], "\n";
}
}
}
}
}
$arr = array (0, -1, 2, -3, 1);
$n = sizeof($arr);
findTriplets($arr, $n, -2);
?>
Javascript
<script>
function findTriplets(arr, n, sum)
{
for (let i = 0; i < n - 2; i++) {
for (let j = i + 1; j < n - 1; j++) {
for (let k = j + 1; k < n; k++) {
if (arr[i] + arr[j] + arr[k] == sum) {
document.write(arr[i]+ " "
+ arr[j] + " "
+ arr[k] + "<br>");
}
}
}
}
}
let arr = [ 0, -1, 2, -3, 1 ];
let n = arr.length;
findTriplets(arr, n, -2);
</script>
Complexity Analysis: - Time Complexity: O(n3).
As three nested for loops have been used. - Auxiliary Space: O(1).
As no data structure has been used for storing values.
Method 2: Hashing. Approach:
Hashing can be used to solve this problem. HashTable or HashMaps allows us to perform
lookup or search operations in constant time complexity. If one can find that for every possible duplet there is an element already existing in the array which can make sum=target sum then the problem will be solved in an efficient manner.
To implement Hashing, we can use unordered_set in C++ or HashSet in Java.
- As we fix first pointer(say a), traverse the array using second pointer(say b) and keep storing the elements encountered in a HashTable.
- As soon as we find that the element which is equal to remaining sum (Target sum -(a+b)) that is already present in the HashTable, we print our triplet.
Algorithm: - Start the outer loop from i=0
till the (n-2)th index.
- For every iteration make an unordered set and enter the inner loop.
- Start the inner loop[ from j = (i+1)(as the values with which we have already checked will not appear in a valid triplet) till last index.
- Check if the element x = Target -(arr[i] + arr[j]) is present then the triplet is found and hence printed.
- Else push the value in the set as for later reference.
- Increment i and Goto step 2.
Pseudo Code: Run a loop from i=0 to n-2
Create an empty hash table
Run inner loop from j=i+1 to n-1
If -(arr[i] + arr[j]) is present in hash table
print arr[i], arr[j] and -(arr[i] + arr[j])
Else
Insert arr[j] in hash table.Implementation: C++#include <bits/stdc++.h>
using namespace std;
void findTriplets(int arr[], int n, int sum)
{
for (int i = 0; i < n - 1; i++) {
unordered_set<int> s;
for (int j = i + 1; j < n; j++) {
int
x = sum - (arr[i] + arr[j]);
if (s.find(x) != s.end())
printf("%d %d %d\n", x, arr[i], arr[j]);
else
s.insert(arr[j]);
}
}
}
int main()
{
int arr[] = { 0, -1, 2, -3, 1 };
int sum = -2;
int n = sizeof(arr) / sizeof(arr[0]);
findTriplets(arr, n, sum);
return 0;
}
Javaimport java.util.*;
class GFG {
static void findTriplets(int arr[], int n, int sum)
{
for (int i = 0; i < n - 1; i++) {
HashSet<Integer> s = new HashSet<>();
for (int j = i + 1; j < n; j++) {
int x = sum - (arr[i] + arr[j]);
if (s.contains(x))
System.out.printf(
"%d %d %d\n", x, arr[i], arr[j]);
else
s.add(arr[j]);
}
}
}
public static void main(String[] args)
{
int arr[] = { 0, -1, 2, -3, 1 };
int sum = -2;
int n = arr.length;
findTriplets(arr, n, sum);
}
}
Python3import math as mt
def
findTriplets(arr, n, Sum):
for i in range(n - 1):
s = dict()
for j in range(i + 1, n):
x = Sum - (arr[i] + arr[j])
if x in s.keys():
print(x, arr[i], arr[j])
else:
s[arr[j]] = 1
arr =
[ 0, -1, 2, -3, 1 ]
Sum = -2
n = len(arr)
findTriplets(arr, n, Sum)
C#using System;
using System.Collections.Generic;
public class GFG {
static void findTriplets(int[] arr, int n, int sum)
{
for
(int i = 0; i < n - 1; i++) {
HashSet<int> s = new HashSet<int>();
for (int j = i + 1; j < n; j++) {
int x = sum - (arr[i] + arr[j]);
if (s.Contains(x))
Console.Write("{0} {1} {2}\n", x, arr[i], arr[j]);
else
s.Add(arr[j]);
}
}
}
public static void Main(String[] args)
{
int[] arr = { 0, -1, 2, -3, 1 };
int
sum = -2;
int n = arr.Length;
findTriplets(arr, n, sum);
}
}
Javascript<script>
function findTriplets(arr,n,sum)
{
for (let i = 0; i < n - 1; i++) {
let s = new Set();
for (let j = i + 1; j < n; j++) {
let x = sum - (arr[i] + arr[j]);
if (s.has(x))
document.write( x+" "+ arr[i]+" "+ arr[j]+"<br>");
else
s.add(arr[j]);
}
}
}
let arr=[0, -1, 2, -3, 1];
let sum = -2;
let n = arr.length;
findTriplets(arr, n, sum);
</script>
Complexity Analysis: - Time Complexity: O(n2).
Use of a nested for loop brings the time complexity to n2. - Auxiliary Space: O(n).
As an unordered_set
data structure has been used for storing values.
Method 3: This method uses the method of Sorting and Two-pointer Technique to solve the above problem. This execution will involve O(n2)) time complexity and O(1) space complexity. The idea is based on Method 2 of this post. Approach : The two pointer
technique can be brought into action using the sorting technique. In two pointer technique one can search for the pair having a target sum in linear time. The idea here is to fix one pointer (say a) and use the remaining pointers to find the pair having required sum Target-value at(a) efficiently.
Now let’s discuss how we can find the required pair effectively using two pointer technique. The pointers used for two pointer
technique are say (l and r). - So if the sum = value(a) + value(l) + value(r) exceeds the required sum, for same (a, l) the required value(r) should be less than the previous. Thus, decrementing the r pointer.
- If the sum = value(a) + value(l) + value(r) is less than the required sum, for same (a, r) the required value(l) should be
greater than the previous. Thus, incrementing the l pointer.
Algorithm: - Sort the array and for every element arr[i] search for the other two elements arr[l], arr[r] such that arr[i]+arr[l]+arr[r]=Target sum.
- Searching for the other two elements can be done efficiently using Two-pointer technique as the array is sorted.
- Run an outer loop taking
control variable as i and for every iteration initialize a value l which is the first pointer with i+1 and r with last index.
- Now enter into a while loop which will run till the value of l<r.
- If arr[i]+arr[l]+arr[r]>Target sum then decrement r by 1 as the required sum is less than the current sum and decreasing the value of will do the
needful.
- If arr[i]+arr[l]+arr[r]<Target sum then increment l by 1 as the required sum is less than the current sum and increasing the value of will do the needful.
- If arr[i]+arr[l]+arr[r]==Target sum print the values.
- Increment i Goto Step 3.
Pseudo Code : 1. Sort all element of array
2. Run loop from i=0 to n-2.
Initialize two index variables l=i+1 and r=n-1
4. while (l < r)
Check sum of arr[i], arr[l], arr[r] is
given sum or not if sum is 'sum', then print
the triplet and do l++ and r--.
5. If sum is less than given sum then l++
6. If sum is greater than given sum then r--
7. If not exist in array then print not found.Implementation: C++#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> findTriplets(int nums[],int n,int sumTarget) {
vector<vector<int>> res;
if(n <=2) return res;
sort(nums,nums + n);
for(int i=0;i<n;i++){
if(i>0 && nums[i] == nums[i-1])
continue;
int num = nums[i];
int target = sumTarget - num;
for(int l=i+1, r=n-1; l<r; ) {
if(nums[l]+nums[r] > target)
r--;
else if (nums[l]+nums[r] < target)
l++;
else {
res.push_back({nums[i], nums[l], nums[r]});
while( l<n-1 && nums[l]==nums[l+1]) l++;
while( r>0 && nums[r]==nums[r-1]) r--;
l++;
r--;
}
}
}
return res;
}
int main()
{
int arr[] = { 0, -1, 2, -3, 1, -1, 3, 0};
int sum = -2;
int
n = sizeof(arr) / sizeof(arr[0]);
vector<vector<int>> res = findTriplets(arr, n, sum);
cout<<"Unique triplets found are : \n";
for(int i = 0;i<res.size();i++)
cout<<res[i][0]<<" "<<res[i][1]<<" "<<res[i][2]<<"\n";
return 0;
}
Javaimport java.io.*;
import java.util.*;
class GFG {
static void findTriplets(int[] arr,
int
n, int sum)
{
Arrays.sort(arr);
for (int i = 0;
i < n - 1; i++) {
int l = i + 1;
int r = n - 1;
int x = arr[i];
while (l < r) {
if (x + arr[l] + arr[r] == sum) {
System.out.println(
x + " " + arr[l] + " "
+ arr[r]);
l++;
r--;
}
else if (x + arr[l] + arr[r] < sum)
l++;
else
r--;
}
}
}
public static void main(String args[])
{
int[] arr = new int[] { 0, -1, 2, -3, 1 };
int sum = -2;
int
n = arr.length;
findTriplets(arr, n, sum);
}
}
Python3def findTriplets(arr, n, sum):
arr.sort();
for i in range(0, n - 1):
l = i + 1;
r = n - 1;
x = arr[i];
while (l < r) :
if
(x + arr[l] + arr[r] == sum) :
print(x, arr[l], arr[r]);
l = l + 1;
r = r - 1;
elif (x + arr[l] + arr[r] < sum):
l = l + 1;
else:
r = r - 1;
arr =
[ 0, -1, 2, -3, 1 ];
sum = -2;
n = len(arr);
findTriplets(arr, n, sum);
C#using System;
class GFG {
static void findTriplets(int[] arr,
int n, int sum)
{
Array.Sort(arr);
for
(int i = 0; i < n - 1; i++) {
int l = i + 1;
int r = n - 1;
int x = arr[i];
while (l < r) {
if (x + arr[l] + arr[r] == sum) {
Console.WriteLine(x + " " + arr[l] + " " + arr[r]);
l++;
r--;
}
else if (x + arr[l] + arr[r] < sum)
l++;
else
r--;
}
}
}
static int Main()
{
int[] arr = new int[] { 0, -1, 2, -3, 1 };
int sum = -2;
int n = arr.Length;
findTriplets(arr, n, sum);
return 0;
}
}
PHP<?php
function findTriplets($arr, $n, $sum)
{
sort($arr);
for ($i
= 0; $i < $n - 1; $i++)
{
$l = $i + 1;
$r = $n - 1;
$x = $arr[$i];
while ($l < $r)
{
if ($x + $arr[$l] +
$arr[$r] == $sum)
{
echo $x, " ", $arr[$l],
" ", $arr[$r], "\n";
$l++;
$r--;
}
else if ($x + $arr[$l] +
$arr[$r] < $sum)
$l++;
else
$r--;
}
}
}
$arr = array(0, -1, 2, -3, 1);
$sum = -2;
$n = sizeof($arr);
findTriplets($arr, $n, $sum);
?>
Javascript<script>
function findTriplets(arr, n, sum)
{
arr.sort(function(a, b){return a - b});
for (let i = 0; i < n - 1; i++) {
let l = i + 1;
let r = n - 1;
let x = arr[i];
while (l < r) {
if (x + arr[l] + arr[r] == sum)
{
document.write(x + " " + arr[l] + " " + arr[r] + "</br>");
l++;
r--;
}
else if (x + arr[l] + arr[r] < sum)
l++;
else
r--;
}
}
}
let arr = [ 0, -1, 2, -3, 1 ];
let sum = -2;
let n = arr.length;
findTriplets(arr, n, sum);
</script>
Output Unique triplets found are :
-3 -1 2
-3 0 1
-1 -1 0 Complexity Analysis: - Time Complexity: O(n2).
Use of a nested loop (one for iterating, other for two-pointer technique) brings the time complexity to O(n2). - Auxiliary Space: O(1).
As no use of additional data structure is used.
How do you find all triplets in an array?
Take three pointers i, j, k.. Initialize i with zero and start a nested loop for i.. Initialize j with (i+1) and start a nested loop for j.. Initialize k with (j+1) and start a loop for k.. If Target == arr[i] + arr[j] + arr[k] break the loop and print values of arr[i], arr[j], arr[k].. How do you find triplets in an array Python?
Practical Data Science using Python. 0 <= i < j < k < number of elements in nums.. |nums[i] - nums[j]| <= a.. |nums[j] - nums[k]| <= b.. |nums[i] - nums[k]| <= c.. How do you get triplets from a list in Python?
Given a list of integers, write a Python program to find all triplets that sum up to given integer 'k'. In this approach, we use two for loops. The first loop sets first element, another to check whether other two elements including first sums up to k or not. This approach takes O(n2) time complexity.
What are triplets in array?
What are triplets in an array? The triplet of an array is a tuple of three elements of different indices, represented by (i, j, k).
| 
