Triplet Sum in Array

Given an array arr of size n and an integer X. Find if there's a triplet in the array which sums up to the given integer X.

Example 1:

Input:
n = 6, X = 13
arr[] = [1 4 45 6 10 8]
Output:
1
Explanation:
The triplet {1, 4, 8} in 
the array sums up to 13.

Example 2:

Input:
n = 5, X = 10
arr[] = [1 2 4 3 6]
Output:
1
Explanation:
The triplet {1, 3, 6} in 
the array sums up to 10.

method: sorting

1. Sort the given array.
2. Loop over the array and fix the first element of the possible triplet, arr[i].
3. Then fix two pointers, one at i + 1 and the other at n – 1. And look at the sum, 
   • If the sum is smaller than the required number, increment the first pointer.
   • Else, If the sum is bigger, decrease the end pointer to reduce the sum.
   • Else, if the sum of elements at two-pointer is equal to given number return true.

c++ implementation:

bool find3Numbers(int a[], int n, int x)
    {
        sort(a,a+n);
    
    for(int i=0;i<n;i++)
    {
        int l=i+1;int r=n-1;
        while(l<r)
        {
            if(a[i]+a[l]+a[r]==x)
            return 1;
            
            else if(a[i]+a[l]+a[r]>x)
            r--;
            
            else
            l++;
        }
    }
    return 0;
    }

Time Complexity: O(n2) 

space Complexity: O(1)