C++ program to find the triplets with a given sum in an array

In this tutorial, we will learn how to write a simple C++ program to find the triplets with a given sum in an array. Before proceeding to the solution, let us understand the problem first.

To understand this problem statement, let us consider a simple example :
Consider an array of size n and a given sum value, we have to find the number of possible triplets whose sum equals to the given sum value. If the given array is {2,5,1,0,3} and the given sum value is 6, then the number of possible triplets that can be formed from this array whose sum=6 are (2,1,3) and (5,1,0).

Find the triplets with a given sum in an array in C++

Method 1

This is the basic approach to solve the given problem where all the possible triplets are generated and their sum is compared with the given sum value. If the sum of a particular triplet matches with the given sum, then that triplet is displayed as output. If no such triplet is found, then an appropriate error message is displayed on the screen. The following code shows the implementation part:

#include <iostream>
using namespace std;
int main()
{
    int arr[]={5,3,8,7,9,1,0,2,6,4};
    int sum=8;
    int i,j,k,c,n,find=0;
    n=sizeof(arr)/sizeof(arr[0]);
    for(i=0;i<n;i++)
    {
        for(j=i+1;j<n;j++)
        {
            for(k=j+1;k<n;k++)
            {
                c=arr[i]+arr[j]+arr[k];
                if(c==sum)
                {
                    cout<<"("<<arr[i]<<","<<arr[j]<<","<<arr[k]<<")\n";
                    find=1;
                }
            }
        }
    }
    if(find==0)
    cout<<"No triplet found!";
    return 0;
}

Output:

(5,3,0)
(5,1,2)
(3,1,4)
(7,1,0)
(0,2,6)

The above code has a time complexity of O(n^3).

Method 2

This is another approach to solve the given problem i.e., C++ program to find the triplets with a given sum in an array where the array is sorted. The triplets are generated between a given range and the value of the range is altered based on the given sum value. If the sum of a particular triplet matches with the given sum, then that triplet is displayed as output. If no such triplet is found, then an appropriate error message is displayed on the screen. The following code shows the implementation part:

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int arr[]={5,3,8,7,9,1,0,2,6,4};
    int sum=8;
    int left,right,i,n,sum1,find=0;
    n=sizeof(arr)/sizeof(arr[0]);
    sort(arr,arr+n);
    for(i=0;i<n-2;i++)
    {
        left=i+1;
        right=n-1;
        sum1=sum-arr[i];
        while(left<right)
        {
            if(arr[left]+arr[right]==sum1)
            {
                cout<<"("<<arr[i]<<","<<arr[left]<<","<<arr[right]<<")\n";
                find=1;
                left++;
                right--;
            }
            else if(arr[left]+arr[right]<sum1)
            {
                left++;
            }
            else if(arr[left]+arr[right]>sum1)
            {
                right--;
            }
        }
    }
    if(find==0)
    cout<<"No triplet found!";
    return 0;
}

Output:

(0,1,7)
(0,2,6)
(0,3,5)
(1,2,5)
(1,3,4)

The above code has a time complexity of O(n^2).

Recommended blogs:
C++ program to sort an array of strings alphabetically
C++ program to print the boundary elements of a matrix

Leave a Reply

Your email address will not be published. Required fields are marked *