Four Sum

Given an array of integers, find all combination of four elements in the array whose sum is equal to a given value X.

Idea :
    1) Find all pair sum, requires O(n^2) space
    2) Sort the pair sum.
    3) Find the 4 elements(2 pairs) using the approach in two pair sum solution in O(n^2) time.

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 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97

#include <iostream> using namespace std; struct pairSum{ int sum, first, second; }; void findPairSum(int *arr, struct pairSum *temp, int n){ int k = 0; for(int i = 0; i < n; i++){ for(int j = i + 1; j < n; j++){ temp[k].sum = arr[i] + arr[j]; temp[k].first = arr[i]; temp[k].second = arr[j]; k++; } } } void merger(struct pairSum *arr, struct pairSum *temp, int low, int mid, int high){ int i = low, j = mid + 1, k = low; while(i <= mid && j <= high){ if(arr[i].sum <= arr[j].sum){ temp[k].sum = arr[i].sum; temp[k].first = arr[i].first; temp[k].second = arr[i].second; k++; i++; } else{ temp[k].sum = arr[j].sum; temp[k].first = arr[j].first; temp[k].second = arr[j].second; k++; j++; } } while(i <= mid){ temp[k].sum = arr[i].sum; temp[k].first = arr[i].first; temp[k].second = arr[i].second; k++; i++; } while(j <= high){ temp[k].sum = arr[j].sum; temp[k].first = arr[j].first; temp[k].second = arr[j].second; k++; j++; } for(int i = low; i<= high; i++){ arr[i].sum = temp[i].sum; arr[i].first = temp[i].first; arr[i].second = temp[i].second; } } void mergeSort(struct pairSum *arr, struct pairSum *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); } } void find4Numbers(struct pairSum *arr, int sz, int x){ struct pairSum *sorted = new pairSum[sz]; int l = 0, r = sz - 1, sum; mergeSort(arr, sorted, 0, sz - 1); while(l < r){ sum = sorted[l].sum + sorted[r].sum; if(sum == x && (sorted[l].first != sorted[r].first && sorted[l].first != sorted[r].second && sorted[l].second != sorted[r].first && sorted[l].second != sorted[r].second)){ cout << "Four elements : " << sorted[l].first << ", " << sorted[l].second << ", " << sorted[r].first << ", " << sorted[r].second << endl; return; } else if(sum > x){ r--; } else{ l++; } } cout << "No 4 elements found!" << endl; return; } int main(){ int arr[] = {1, 4, 45, 6, 10, 12}; int x = 56; int n = sizeof(arr)/sizeof(arr[0]); int sz = n * (n - 1) / 2; struct pairSum *pairSums = new struct pairSum[sz]; findPairSum(arr, pairSums, n); find4Numbers(pairSums, sz, x); return 0; }