Given an array arr[] of size "n" and an integer "x," the task is to find if there is a triplet in the array that sums up to the given integer "x".
Example
Input: arr[] = {1, 2, 4, 3, 6}, n = 5, x = 10, Output: true
Example
Input: arr[] = {1, 2, 4, 6}, n = 4, x = 10, Output: false
Solutions
Method 1: In O(n^2) time and O(1) space
This method includes sorting the array, fixing the first number, and finding the remaining two numbers using two pointers.
The idea is loop over the sorted array and fix the first element of the possible triplet, arr[i].
Then run a while loop until j < k, where j = i + 1 and k = n – 1 and do the following:
1) If the sum (arr[i] + arr[j] +arr[k]) is smaller than the required sum, increment j (j++).
2) Else, if the sum is bigger, decrement k, (k--).
3) Else, if the sum is equal to the given number (n), then return "true."
Complexity
The time complexity of this solution is O(n^2) and space complexity is O(1).