3 Sum

Given an array and a value, find if there is a triplet in array whose sum is equal to the given value. If there is such a triplet present in array, then print the triplet and return true. Else return false.

Approach:

    1) Sort the input array.

    2) Fix the first element as A[i] where i is from 0 to array size - 2. After fixing the first element of triplet, find the other two elements using the technique used in 2 Sum problem.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68

#include <iostream> using namespace std; void merger(int *arr, int *temp, int low, int mid, int high){ int i, j, k; i = low; j = mid + 1; k = low; while(i <= mid && j <= high){ if(arr[i] <= arr[j]){ temp[k++] = arr[i++]; } else{ temp[k++] = arr[j++]; } } while(i <= mid){ temp[k++] = arr[i++]; } while(j <= high){ temp[k++] = arr[j++]; } for(int i = low; i <=high; i++){ arr[i] = temp[i]; } } void mergeSort(int *arr, int *temp, int low, int high){ if(low < high){ int mid = (low + high) / 2; mergeSort(arr, temp, low, mid); mergeSort(arr, temp, mid + 1, high); merger(arr, temp, low, mid, high); } } int find3Numbers(int *arr, int n, int sum){ int *temp = new int[n]; mergeSort(arr, temp, 0, n - 1); int curSum, left, right; for(int i = 0; i < n - 2; i++){ left = i + 1; right = n - 1; while(left < right){ curSum = arr[i] + arr[left] + arr[right]; if(curSum == sum){ cout << "Triplet : " << arr[i] << " " << arr[left] << " " << arr[right] << " " << endl; return 1; } else if(curSum < sum){ left++; } else{ right--; } } } return 0; } int main(){ int arr[] = {1, 4, 45, 6, 10, 8}; int sum = 51; int n = sizeof(arr)/sizeof(arr[0]); if(find3Numbers(arr, n, sum)){ ; } else{ cout << "No such triplet exists!" << endl; } return 0; }