- 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.

^{3})

## 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.

^{2})#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.

^{2})