Find Triplet Whose Sum is Equal to Given Number

• Write a program to find three elements of given array whose sum is equal to K
• Algorithm to find a triplet whose sum is equal to given number.

Given an integer array of size N and an integer K. We have to find three array elements whose sum is equal to K.
For Example :

```Input Array : 23, 8, 7, 7, 1, 9, 10, 4, 1, 3
K = 17
Output : 7, 7, 3
```

Let inputArray be an integer array of size N and we want to find a triplet whose sum is K.

Brute Force Approach
• Using three for loops, generate all possible combinations of triplets and compare their sum with K. If sum of triplet is equal to K then print otherwise continue.
Time Complexity : O(n3)

C program to find triplet whose sum is given number

```#include<stdio.h>

int isTripletSum(int *array, int size, int K) {
int i, j, k;

/* Brute Force Approach : Check the sum of all
possibel combinations of triplets */
for(i = 0; i < size-2; i++) {
for (j = i+1; j < size-1; j++) {
for (k = j+1; k < size; k++) {
/* Check if the sum of current triplets
is equal to "K" */
if(array[i] + array[j] + array[k] == K) {
printf("Triplet Found : %d, %d, %d", array[i], array[j], array[k]);
return 1;
}
}
}
}
/* No triplet found whose sum is equal to K */
return 0;
}

int main() {
int array[10] = {23, 8, 7, 7, 1, 9, 10, 4, 1, 3};
/* find a triplet whose sum is 17 */
if(!isTripletSum(array, 10, 17)){
printf("No Triplet Found");
}

return 0;
}
```
Output
```Triplet Found : 7, 7, 3
```

By Sorting Input Array
Let firstIndex, secondIndex and thirdIndex are three integer variables.
• Sort inputArray using any O(nLogn) average time sorting algorithm like quick sort or merge sort.
• Initialize firstIndex to 0. Using firstIndex traverse inputArray from index 0 to N-2 and fix first element of triplet.
• Now, we have to find two array elements whose sum is equal to K-inputArray[firstIndex]. Let S = K-inputArray[firstIndex]
• Initialize secondIndex and thirdIndex to firstIndex+1 and N-1.(secondIndex=firstIndex+1; thirdIndex=N-1)
• If the sum of second and third element is equal to S, then we found one triplet.
• If the sum of second and third element is less than S, increment seconIndex else decrement third index.
• Continue until secondIndex < thirdIndex.
Time Complexity : O(n2)
```#include <stdio.h>

/* Swap array element at index left and right */
void swap(int array[], int left, int right) {
int temp;
/* Swapping using a temp variable */
temp = array[left];
array[left]=array[right];
array[right]=temp;
}

void quickSort(int array[], int left, int right) {
int pivot;
if (right > left) {
/* Partition the given array into
two segment by calling partion function */
pivot = partition(array, left, right);

/* Recursively sort left and right sub array*/
quickSort(array, left, pivot-1);
quickSort(array, pivot+1, right);
}
}

int partition(int array[], int left, int right) {
int temp = left;
int pivot = array[left];

while(left < right) {
/* From left side, search for a number
greater than pivot element */
while(array[left] <= pivot)
left++;
/* From right side, search for a number
less than pivot element */
while(array[right] > pivot)
right--;

/*Swap array[left] and array[right] */
if(left < right)
swap(array, left, right);
}
/* Put pivot element in it's currect position '*/
array[temp] = array[right];
array[right] = pivot;
/* Return partition index. All elements left of
right index is < pivot whereas elements right
side of right index are > pivot element */
return right;
}

/*
This function prints triplet whose sum is equal to K
*/
int isTripletSum(int *array, int size, int K) {
int first, second, third, currentSum, sum;

/* Sort elements of array using quick sort algorithm  */
quickSort(array, 0, size-1);

/* Fix first element */
for(first = 0; first < size-2; first++) {
/* Initialize second and third to next element of first and
last index of array respectively */
second = first+1;
third = size-1;
/* sum id the remianing value of K to be found */
sum = K - array[first];
while(second < third) {
currentSum = array[second] + array[third];
/*Check if sun of array[second] and array[third]
is equal to sum */
if(currentSum == sum) {
printf("Triplet found : %d, %d, %d\n", array[first],
array[second], array[third]);
return 1;
} else if(currentSum < sum) {
/* If currentSum < sum, then increase the value
of currentSum by incrementing left index */
second++;
} else {
/* currentSum is greater than sum, decrease
value of currentsum by decrementing right index */
third--;
}
}
}
return 0;
}

int main(){
int array[10] = {23, 8, 7, 7, 1, 9, 10, 4, 1, 3};
/* find a triplet whose sum is 17 */
if(!isTripletSum(array, 10, 17)){
printf("No Triplet Found");
}

return 0;
}
```
Output
```Triplet found : 1, 7, 9
```

Using Hash Table
Algorithm to find three numbers whose sum is equal to K using hash table.
• Traverse inputArray and put each element in hash table.
• Using two for loops, generate all possible combinations of two elements and find their sum. Let S = inputArray[i] + inputArray[j].
• Check if (K-S) exists in hash table. If true then we found a triplet (inputArray[i], inputArray[j] and K-S) whose sum is K.
Time Complexity : O(n2)