Problem Statement
An array of integers and a target sum are given, find out if there is any triplet whose sum is equal to the given target sum exists in the array or not, print the triplet, if a triplet sum in array is present and return true. Otherwise, return false.
Example
Input-1
Array[] : [1, 2, 3, 4, 5, 6]
Target : 9
Output-1
1, 2, 6
Explanation
Within the array, there is a triplet (1, 3, and 5) whose sum is 9.
Input-2
Array[] : [0, 1, 5, 8, 9, 6, 3]
Target : 5
Output-2
Triplet does not exist.
Explanation
There is no triplet sum in array that exists in the array which has a sum equal to given target 5.
Constraints
1 <= array.length <= 10^3
-10^6 <= arr[i] <= 10^6
-10^9 <= Target <= 10^9
Approach 1- Naive Approach
Intuition:
The simple approach to the above mentioned problem is to generate all the possible triplets and compare each triplet’s sum to the given value. The below algorithm implements this naive approach of triplet sum in array using three nested loops.
Algorithm
- A sum “target” and an array of length n are given.
- Construct three nested for loops, where first loop counter i runs from arr[0] to end, where i ranges from 0 to N.
- Second loop counter j runs from arr[1] to end, where i ranges from i+1 to N.
- Third loop counter k runs from arr[2] to end, where i ranges from i+2 to N.
- Find the sum of the ith, jth, and kth elements. if the sum matches the given target. Print the values and break from the loop.
- Otherwise return false, if no triplet was found.
Code Implementation
Code in C++
#include <bits/stdc++.h>
using namespace std;
// returns true, if there is triplet with sum equal
// to 'target' exists in arr[] and print that triplet also.
bool findTriplet(int arr[], int n, int target)
{
// Fix the first element as arr[i]
for (int i = 0; i < n - 2; i++)
{
// Fix the second element as arr[j]
for (int j = i + 1; j < n - 1; j++)
{
// Now find the third value
for (int k = j + 1; k < n; k++)
{
if (arr[i] + arr[j] + arr[k] == target)
{
cout << "Triplet is " << arr[i] <<
", " << arr[j] << ", " << arr[k];
return true;
}
}
}
}
// No triplet was found
return false;
}
/* Driver code */
int main()
{
int arr[] = { 1, 2, 3, 4, 5, 6 };
int target = 9;
int n = sizeof(arr) / sizeof(arr[0]);
findTriplet(arr, n, target);
return 0;
}
Code in Java
// Java program to find a triplet sum in array
class Main{
boolean findTriplet(int arr[], int n, int target){
// Fix the first element as A[i]
for (int i = 0; i < n - 2; i++)
{
// Fix the second element as A[j]
for (int j = i + 1; j < n - 1; j++)
{
// Now find the third number
for (int k = j + 1; k < n; k++)
{
if (arr[i]+arr[j]+arr[k] == target){
System.out.print("Triplet is " + arr[i] + ", "
+ arr[j] + ", " + arr[k]);
return true;
}
}
}
}
// If we reach here, then no triplet was found
return false;
}
// Driver program to test above functions
public static void main(String[] args)
{
Main triplet = new Main();
int arr[] = { 1, 2, 3, 4, 5, 6 };
int target = 9;
int n = arr.length;
triplet.findTriplet(arr, n, target);
}
}
Code in Python
# Python3 program to find a triplet sum in array
# that sum to a given value
def findTriplet(arr, n, target):
# Fix the first element as arr[i]
for i in range( 0, n-2):
# Fix the second element as arr[j]
for j in range(i + 1, n-1):
# Now find the third number
for k in range(j + 1, n):
if arr[i] + arr[j] + arr[k] == target:
print("Triplet is", arr[i],
", ", arr[j], ", ",arr[k])
return True
# triplet not found
return False
# Driver program to test above function
arr = [1, 2, 3, 4, 5, 6 ];
target = 9;
n = len(arr)
findTriplet(arr, n, target)
Output
Triplet is 1, 2, 6
Time Complexity
The time complexity is O(n^3). Since there are three nested loops that traverse the array.
Space Complexity
The space complexity is O(1). Since no extra space is used in the solution of triplet sum in array.
Approach 2- Using Recursion
Intuition:
Recursion is used in this solution, and the concept is similar to the 0-1 Knapsack problem. For each item, we either consider the current number or leave it out and repeat for the remaining numbers. If we include or exclude the current item and we get the desired sum, return true.
Algorithm
- Create a recursive function to check if a triplet sum in array exists with the given sum.
- The recursion function takes an array, array length, target sum, and current count for the triplet.
- Check if the triplet has the desired sum, If yes return true.
- Otherwise, return false if the sum is negative with the current conditions.
- At last, return the recursion function with two conditions (including and excluding the current number).
Code Implementation
Code in C++
#include <iostream>
using namespace std;
// Naive recursive function
bool findTriplet(int arr[], int n, int target, int count)
{
// return true, if triplet has the desired sum.
if (count == 3 && target == 0) {
return true;
}
// if the sum is negative the current configuration, return false.
if (count == 3 || n == 0 || target < 0) {
return false;
}
// return again with including and excluding the current number
return findTriplet(arr, n - 1, target - arr[n - 1], count + 1) ||
findTriplet(arr, n - 1, target, count);
}
int main()
{
int arr[] = {0, 1, 5, 8, 9, 6, 3};
int target = 5;
int n = sizeof(arr) / sizeof(arr[0]);
findTriplet(arr, n, target, 0) ? cout << "Triplet exists":
cout << "Triplet does not exist";
return 0;
}
Code in Java
class Main
{
// Naive recursive function
static boolean findTriplet(int[] arr, int n, int target, int count)
{
// if triplet has the desired sum, return true
if (count == 3 && target == 0) {
return true;
}
// return false if the sum is not possible
if (count == 3 || n == 0 || target < 0) {
return false;
}
// recur with including and excluding the current element
return findTriplet(arr, n - 1, target - arr[n - 1], count + 1) ||
findTriplet(arr, n - 1, target, count);
}
public static void main(String[] args)
{
int arr[] = {0, 1, 5, 8, 9, 6, 3};
int target = 5;
if (findTriplet(arr, arr.length, target, 0)) {
System.out.println("Triplet exists");
}
else {
System.out.println("Triplet does not exist");
}
}
}
Code in Python
# Naive recursive function
def isTripletExist(nums, n, target, count):
# if triplet has the desired sum, return true
if count == 3 and target == 0:
return True
# return false if the sum is not possible with the current configuration
if count == 3 or n == 0 or target < 0:
return False
# recur with including and excluding the current element
return isTripletExist(nums, n - 1, target - nums[n - 1], count + 1) or\
isTripletExist(nums, n - 1, target, count)
if __name__ == '__main__':
nums = [0, 1, 5, 8, 9, 6, 3]
target = 5
if isTripletExist(nums, len(nums), target, 0):
print('Triplet exists')
else:
print('Triplet does not exist')
Output
Triplet does not exist
Time Complexity
The time complexity is O(3^n). Since we need three numbers in a triplet, the Base condition will hit for each number.
Space Complexity
The space complexity is O(N). Since recursion takes more memory for constants to find triplet sum in array.
Approach 3- Hashing-Based Solution – Using HashSet
Intuition:
Run the inner loop from position i+1 to position n, then the outer loop from start to end. Create a HashSet and store the elements from i+1 to j-1 in it. Check to see whether there is a number in the set that equals target – arr[i] – arr[j] if the given sum is the target.
Algorithm
- From start to end, go through all the array elements with loop counter i.
- Create a HashSet to store the unique pairs.
- Run the second for loop from position i+1 until the end of the array.
- If there is any number exists in the Hashset which is equal to target- arr[i] – arr[j], then print the triplet (arr[i], arr[j], target-arr[i]-arr[j]) and break from the loop.
- Put the jth element in the HashSet.
Code Implementation
Code in C++
// C++ program to find a triplet sum in array using Hashing
#include <bits/stdc++.h>
using namespace std;
bool findTriplet(int A[], 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> s;
int curr_sum = sum - A[i];
for (int j = i + 1; j < arr_size; j++)
{
if (s.find(curr_sum - A[j]) != s.end())
{
printf("Triplet is %d, %d, %d", A[i],
A[j], curr_sum - A[j]);
return true;
}
s.insert(A[j]);
}
}
// If no triplet was found
return false;
}
int main()
{
int A[] = { 1, 2, 3, 4, 5, 6};
int sum = 9;
int arr_size = sizeof(A) / sizeof(A[0]);
findTriplet(A, arr_size, sum);
return 0;
}
Code in Java
// Java program to find a triplet sum in array using Hashing
import java.util.*;
class Main{
static boolean findTriplet(int A[], int arr_size, int sum)
{
// Fix the first element
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]
HashSet<Integer> s = new HashSet<Integer>();
int curr_sum = sum - A[i];
for (int j = i + 1; j < arr_size; j++)
{
if (s.contains(curr_sum - A[j]))
{
System.out.printf("Triplet is " +A[i]+", "+A[j]+", "+
(curr_sum - A[j]));
return true;
}
s.add(A[j]);
}
}
// If no triplet was found
return false;
}
public static void main(String[] args)
{
int A[] = { 1, 2, 3, 4, 5, 6 };
int sum = 9;
int arr_size = A.length;
findTriplet(A, arr_size, sum);
}
}
Code in Python
# Python3 program to find a triplet sum in array using Hashing
def findTriplet(A, arr_size, sum):
for i in range(0, arr_size-1):
# Find pair in subarray A[i + 1..n-1]
# with sum equal to sum - A[i]
s = set()
curr_sum = sum - A[i]
for j in range(i + 1, arr_size):
if (curr_sum - A[j]) in s:
print("Triplet is", A[i],
", ",A[j],", ",curr_sum-A[j])
return True
s.add(A[j])
return False
# Driver program to test above function
A = [1, 2, 3, 4, 5, 6]
sum = 9
arr_size = len(A)
findTriplet(A, arr_size, sum)
Output
Triplet is 1, 5, 3
Time Complexity
The time complexity is O(n^2). Since there are two nested loops that traverse the array.
Space Complexity
The space complexity is O(N). Since extra space is used in the solution as HashSet.
Approach 4- Efficient Approach – Using Two-Pointer Technique
Intuition:
The array can be sorted to increase the algorithm’s efficiency. The Two-pointer Technique is used in this effective approach for triplet sum in array. Traverse the array and fix the triplet’s first element. Now find a pair whose sum is equal to target – arr[i] by using the Two Pointers technique.
Algorithm
- Sort the input array of integers.
- Fix the first number of the possible triplet, arr[i], by iterating through the array.
- Then, fix the two pointers, one at index i + 1 and the other at index i – 1. Now look for the sum.
- Increase the first pointer if the sum is less than the required sum.
- Else, Reduce the end pointer if the sum is higher to decrease it.
- Otherwise, print the triplet and break from the loop if the sum of the numbers at the two-pointer equals the given target.
Code Implementation
Code in C++
// C++ program to find a triplet sum in array
#include <bits/stdc++.h>
using namespace std;
bool findTriplet(int arr[], int n, int target)
{
int l, r;
/* Sort the elements */
sort(arr, arr + n);
/* start with the first element */
for (int i = 0; i < n - 2; i++) {
l = i + 1; // index of the first element
r = n - 1; // last element
while (l < r) {
if (arr[i] + arr[l] + arr[r] == target) {
printf("Triplet is %d, %d, %d", arr[i], arr[l],arr[r]);
return true;
}
else if (arr[i] + arr[l] + arr[r] < target)
l++;
else
// A[i] + A[l] + A[r] is greater than target
r--;
}
}
// If no triplet was found
return false;
}
int main()
{
int arr[] = { 1, 2, 3, 4, 5, 6};
int target = 9;
int n = sizeof(arr) / sizeof(arr[0]);
findTriplet(arr, n, target);
return 0;
}
Code in Java
import java.util.*;
// Java program to find a triplet sum in array
class FindTriplet {
boolean findTriplet(int arr[], int n, int sum){
int l, r;
/* Sort the elements */
Arrays.sort(arr);
/* Now fix the first element one by one and find the
other two elements */
for (int i = 0; i < n - 2; i++) {
l = i + 1; // index of the first element
r = n - 1; // index of the last element
while (l < r) {
if (arr[i] + arr[l] + arr[r] == sum) {
System.out.print("Triplet is " + arr[i] + ", "
+ arr[l] + ", " + arr[r]);
return true;
}
else if (arr[i] + arr[l] + arr[r] < sum)
l++;
else
// arr[i] + arr[l] + arr[r] is greater than sum
r--;
}
}
// If no triplet was found
return false;
}
}
class Main{
public static void main(String[] args){
FindTriplet triplet = new FindTriplet();
int[] arr = { 1, 2, 3, 4, 5, 6 };
int sum = 9;
int n = arr.length;
triplet.findTriplet(arr, n, sum);
}
}
Code in Python
# Python3 program to find a triplet sum in array
def find3Numbers(A, arr_size, sum):
# Sort the elements
A.sort()
# Now fix the first element
# one by one and find the
# other two elements
for i in range(0, arr_size-2):
# index of the first element
# in the remaining elements
l = i + 1
# index of the last element
r = arr_size-1
while (l < r):
if( A[i] + A[l] + A[r] == sum):
print("Triplet is", A[i],
', ', A[l], ', ', A[r]);
return True
elif (A[i] + A[l] + A[r] < sum):
l += 1
else: # A[i] + A[l] + A[r] > sum
r -= 1
# If we reach here, then
# no triplet was found
return False
# Driver program to test above function
A = [1, 2, 3, 4, 5, 6]
sum = 9
arr_size = len(A)
find3Numbers(A, arr_size, sum)
Output
Triplet is 1, 2, 6
Time Complexity
The time complexity is O(n^2). Since there are two nested loops that traverse the array.
Space Complexity
The space complexity is O(1). Since no extra space is used in the solution of triplet sum in array.
Approach 5- Printing Distinct Triplets
Intuition:
The approach is to sort the input array in a non decreasing order and check whether a triplet is generated by an element from the array nums[i] and two pairs from nums[i+1….n] for each element in the array nums[i]. The Below implementation of code in Java, C++, and Python shows this intuition.
Algorithm
- Sort the given array in ascending order.
- Check if triplet is formed by nums[i] and a pair from subarray nums[i+1…n].
- Maintain two indices pointing to endpoints of the subarray nums[i+1…n].
- Construct a while loop if low is less than high.
- increase the low index if the total is smaller than the remaining sum.
- decrease the high index if the total is larger than the remaining sum.
- Print the triplet, if the given target is found.
Code Implementation
Code in C++
#include <iostream>
#include <algorithm>
using namespace std;
// Function to print all distinct triplet in an array with the given sum
bool printAllTriplets(int nums[], int n, int target)
{
// sort the array in ascending order
sort(nums, nums + n);
// check if triplet is formed by nums[i] and a pair from
// subarray nums[i+1…n)
for (int i = 0; i <= n - 3; i++)
{
// remaining sum
int k = target - nums[i];
// maintain two indices pointing to endpoints of the
// subarray nums[i+1…n)
int low = i + 1, high = n - 1;
// loop if `low` is less than `high`
while (low < high)
{
// increment `low` index if the total is
// less than the remaining sum
if (nums[low] + nums[high] < k) {
low++;
}
// decrement `high` index if the total is
// more than the remaining sum
else if (nums[low] + nums[high] > k) {
high--;
}
// triplet with the given sum is found
else {
// print the triplet
cout << "Triplet is " <<nums[i]<<" " << nums[low] <<" "<<
nums[high];
return true;
}
}
}
return false;
}
int main()
{
int nums[] = { 1, 2, 3, 4, 5, 6};
int target = 9;
int n = sizeof(nums) / sizeof(nums[0]);
printAllTriplets(nums, n, target);
return 0;
}
Code in Java
import java.util.Arrays;
public class Main
{
public static boolean printAllTriplets(int[] nums, int target)
{
// sort the array in ascending order
Arrays.sort(nums);
int n = nums.length;
// check if triplet is formed by nums[i] and a pair from
// subarray nums[i+1…n)
for (int i = 0; i <= n - 3; i++)
{
// remaining sum
int k = target - nums[i];
// maintain two indices pointing to endpoints of the
// subarray nums[i+1…n)
int low = i + 1;
int high = nums.length - 1;
// loop if `low` is less than `high`
while (low < high)
{
// increment `low` index if the total
// is less than the remaining sum
if (nums[low] + nums[high] < k) {
low++;
}
// decrement `high` index if the total is
// more than the remaining sum
else if (nums[low] + nums[high] > k) {
high--;
}
// triplet with the given sum is found
else {
// print the triplet
System.out.println("Triplet is " + nums[i] + " "
+ nums[low] + " " + nums[high]);
// increment `low` index and decrement `high` index
return true;
}
}
}
return false;
}
public static void main(String[] args)
{
int[] nums = { 1, 2, 3, 4, 5, 6 };
int target = 9;
printAllTriplets(nums, target);
}
}
Code in Python
# Function to print all distinct triplets in the list with the given sum
def printAllTriplets(nums, target):
# sort the list in ascending order
nums.sort()
n = len(nums)
# check if triplet is formed by nums[i] and a pair from
# sublist nums[i+1…n)
for i in range(n - 2):
# remaining sum
k = target - nums[i]
# maintain two indices pointing to endpoints of the
# sublist nums[i+1…n)
(low, high) = (i + 1, n - 1)
# loop if `low` is less than `high`
while low < high:
# increment `low` index if the total
# is less than the remaining sum
if nums[low] + nums[high] < k:
low = low + 1
# decrement `high` index if the total
# is more than the remaining sum
elif nums[low] + nums[high] > k:
high = high - 1
# triplet with the given sum is found
else:
# print the triplet
print("Triplet is",nums[i], nums[low], nums[high])
# increment `low` index and decrement `high` index
return True
return False
if __name__ == '__main__':
nums = [1, 2, 3, 4, 5, 6]
target = 9
printAllTriplets(nums, target)
Output
Triplet is 1 2 6
Time Complexity
The time complexity is O(n^2). Since there are three nested loops that traverse the array.
Space Complexity
The space complexity is O(1). Since no extra space is used in the solution for triplet sum in array.
Conclusion
- We have given an array of integers and a value, We had to find if there is a triplet in the array whose sum is equal to the given value.
- In this problem, We have to print the triplet and also return true, if such a triplet is present in the array. Else return false.
- For eg, If the array is [1, 2, 3, 4, 5, 6] and the given target value is 9, Here one of the triplets within the array is (1, 3, and 5) whose sum is 9.
- The naive approach takes O(n^3^) time complexity as three loops were used, and O(1) space complexity because no extra space is used.
- On the other hand, the most efficient approach of triplet sum in array is Using the Two-pointer Technique takes O(n^2^) time complexity and O(1) as space complexity.
- If there is no triplet found, For eg, If the array is [0, 1, 5, 8, 9, 6, 3] and the given target value is 5. Here print the output as “Triplet does not exist”.
FAQs
Q: How to print all triplets with a given sum?
A: Refer Print all triplets with given sum.
Q: How to print all triplets with a sum equal to zero?
A: Refer Find all triplets with zero sum.
