# C Program to Find Four Elements Whose Sum is Equal to S

• 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, 5
```
We can solve this problem in multiple ways. Here we are going to discuss two approaches of O(n4) and O(n3) 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(n4)
• Using four loops, generate all possible combinations of four elements and array and check if their sum is equal to S.
Time Complexity : O(n4)

## 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;
}
}
}
}
}
}

int main() {
int array = {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(n3)
• 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).
Time Complexity : O(n3)
```#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 = {3, 7, 1, 9, 15, 14, 6, 2, 5, 7};
getFourElementSum(array, 10, 15);
return 0;
}
```
Output
```3, 1, 5, 6
```