## Friday, August 30, 2013

### find four elements in array whose sum equal to a given number X

This can be solved efficiently via using HashTables.

We can have a hashtable sums `sums` will store all possible sums of two different elements. For each sum `S` it returns pair of indexes `i` and `j` such that `a[i] + a[j] == S` and `i != j`. But initially it's empty, we'll populate it on the way. So, this can be done in O(n^2) time.

Pseudocode

```for (int i = 0; i < n; ++i) {
// 'sums' hastable holds all possible sums a[k] + a[l]
// where k and l are both less than i

for (int j = i + 1; j < n; ++j) {
int current = a[i] + a[j];
int rest = X - current;
// Now we need to find if there're different numbers k and l
// such that a[k] + a[l] == rest and k < i and l < i
// but we have 'sums' hashtable prepared for that
if (sums[rest] != null) {
// found it
}
}

// now let's put in 'sums' hashtable all possible sums
// a[i] + a[k] where k < i
for (int k = 0; k < i; ++k) {
sums[a[i] + a[k]] = pair(i, k);
}
}
```

Thanks.