All Unique Triplets that Sum up to a Given Value

We have given an array of integers and a given number called ‘sum’. The problem statement asks to find out the triplet that adds up to the given number ‘sum’.

Table of Contents

Example

Input:

arr[] = {3,5,7,5,6,1}

sum=16

Output:

(3, 7, 6), (5, 5, 6)

Explanation:

Triplet which equals to the given sum.

Input:

arr[] = {3,4,1,5,4}

sum=20

Output:

There are no triplets that can be formed with the given number

Algorithm

Sort the given array.
Set the Boolean variable isFound to false.
While i=0 to i<n-1
1. Set j=i+1, k=n-1.
2. While j<k
  1. Check if three of the elements together add up to the given sum.
    1. If true, then print all three number and set isFound to true.
  2. Check else if the sum of the three elements is greater than the sum.
    1. If true, then decrease the value of k by 1.
  3. Check if the sum of three elements (current array elements) is less than the sum.
    1. If true, then increase the value of j by 1.
Check if isFound remains false, it concludes that no triplets can be formed.

Explanation

We will sort the array first for the values to become in increasing order because we are going to use a binary search approach, a little. We are going to declare a Boolean variable and set its value to false at first, we are going to update it as soon as we found the triplet. This is to make sure that if we will not found any of the triplets which have elements sum to a given number, the value isFound remains as it is, only we are going to update it to true when we found a triplet, so with this, we can conclude that no triplet found.

After sorting the array, starting in the nested loop, we will traverse the array up to the length n-1. Setting one of the variable values as i+1, another value to n-1. In the inner loop, we will traverse through all the values of an array, and check if the given number ‘sum’ is equal to the sum of the three current array elements (arr[i] + arr[j] + arr[k]) is equal or not. If the condition satisfies, we are going to print all the current values of an array and set isFound value to true, it ensures that we should not return a false value.

If the sum of three current values of an array is not equal to the given number, we will check for that if sum of the three current elements is less than the given sum, if it is less than the sum, we will increase the value of j, means our left pointer which indicates from the left traversal is increase and if this condition also doesn’t satisfy we will check for if the sum is greater than the sum, If true, then we will decrease the value of k.

It will go on till all the values of the array will be traversed. And we are going to return the isFound value, which can be returned as true if we found any of the triplets and false if we didn’t found any.

Implementation

C++ program for All Unique Triplets that Sum up to a Given Value

#include<iostream>
#include<algorithm>

using namespace std;

int getTripletOfSum(int arr[], int n, int sum)
{
    int i, j, k;
    bool isFound=false;
    sort(arr, arr + n);
    for(i = 0; i < n - 2; i++)
    {
        j = i + 1;
        k = n - 1;

        while(j < k)
        {
            if(arr[i] + arr[j] + arr[k] == sum)
            {
                cout<<"["<<arr[i]<<" "<<arr[j]<<" "<<arr[k]<<"]"<<endl;
                j++;
                k--;
                isFound=true;
            }
            else if(arr[i] + arr[j] + arr[k] > sum)
                k--;
            else
                j++;
        }
    }
    return isFound;
}
int main()
{
    int nums[] = {3,5,7,5,6,1};
    int n = sizeof(nums) / sizeof(nums[0]);
    int sum = 16;
    if(!getTripletOfSum(nums, n, sum))
        cout << "There are no triplets that can be formed with the given number";

    return 0;
}

[3 6 7]
[5 5 6]

Java program for All Unique Triplets that Sum up to a Given Value

import java.util.Arrays;

public class TripletsWithSum
{
    public static boolean getTripletOfSum(int arr[], int sum)
    {
        Arrays.sort(arr);

        boolean isFound=false;

        for (int i = 0; i < arr.length - 2; i++)
        {
            int j = i + 1;
            int k = arr.length - 1;
            while (j < k)
            {
                if (arr[i] + arr[j] + arr[k] == sum)
                {
                    System.out.println("["+arr[i] + " " + arr[j] +" " +arr[k]+"]");
                    j++;
                    k--;
                    isFound=true;
                }
                else if (arr[i] + arr[j] + arr[k] < sum)
                    j++;

                else
                    k--;
            }
        }
        return isFound;
    }
    public static void main(String[] args)
    {
        int arr[] = {3,5,7,5,6,1};
        int sum = 16;
        if (!getTripletOfSum(arr, sum))
        {
            System.out.println("There are no triplets that can be formed with the given number");
        }
    }
}

[3 6 7]
[5 5 6]