- Write a program to find four numbers whose sum is equal to given number.
- How to find four array elements whose sum id equal to S.

Given an integer array of size N and an integer S. We have to **find four elements whose sum is S**. There may be multiple set of four numbers whose sum is S but we have to print only one such set.

For Example :

Input Array : 3 7 1 9 15 14 6 2 5 7 S = 24 Output : 3, 7, 9, 5We can solve this problem in multiple ways. Here we are going to discuss two approaches of O(n

^{4}) and O(n

^{3}) time complexity.

Let inputArray be an integer array of size N and we want to find 4 elements whose sum is equal to S.

**Brute Force Method : O(n**

^{4})- Using four loops, generate all possible combinations of four elements and array and check if their sum is equal to S.

^{4})

## C program to find four array elements whose sum is equal to given number.

#include <stdio.h> /* This function prints four elements whose sum is equal to SUM */ void getFourElementSum(int *array, int size, int SUM) { /* Using four for loop, generate all possible combinations of four elements and array and check if their sum is equal to SUM */ int i, j, k, l; for(i = 0; i < size-3; i++) { for(j =i+1; j < size-2; j++){ for(k = j+1; k < size-1; k++){ for(l=k+1; l<size; l++){ if(array[i] + array[j] + array[k] + array[l] == SUM){ /* Found four elements whose sum is equal to SUM */ printf("%d, %d, %d, %d\n", array[i],array[j],array[k],array[l]); return; } } } } } printf("Not Found\n"); } int main() { int array[10] = {3, 7, 1, 9, 15, 14, 6, 2, 5, 7}; getFourElementSum(array, 10, 24); return 0; }Output

3, 7, 9, 5

**By Sorting Input Array : O(n**

^{3})- Sort inputArray using any O(nLogn) time complexity algorithm like quick sort or merge sort.
- Using two for loops, fix first two elements. Let it is be A and B.
- Now, we have to find two elements whose sum is equal to S-(A+B).
- We will use the second method of this post to find two number of a sorted array whose sum is equal to S-(A+B).

^{3})

#include <stdio.h> #include <stdlib.h> /* This function will be used as a comparator function by qsort function */ int compare(const void* one, const void* two) { return *(int*)one > *(int*)two; } /* This function prints four elements whose sum is equal to SUM */ void getFourElementSum(int *array, int size, int SUM) { int left, right, i, j, remainingSum; /* sort input array */ qsort(array, size, sizeof(int), compare); /* Fix two elements using two for loops */ for (i = 0; i < size-3; i++) { for (j = i+1; j < size-2; j++){ /* Now this problem reduceto problem of finding a pair in a sorted array(from index j+1 to size-1) whose sum is equal to SUM-array[i]-array[j] */ left = j+1; right = size-1; remainingSum = SUM - array[i] - array[j]; while(left < right) { if(array[left] + array[right] == remainingSum) { printf("%d, %d, %d, %d\n", array[i], array[j], array[left], array[right]); return; } else if (array[left] + array[right] < remainingSum) { left++; } else { right--; } } } } } int main() { int array[10] = {3, 7, 1, 9, 15, 14, 6, 2, 5, 7}; getFourElementSum(array, 10, 15); return 0; }Output

3, 1, 5, 6