Is there any efficient algorithm other than brute force search to find the three integers?

Yep; we can solve this in O(n^{2}) time! First, consider that your problem `P`

can be phrased equivalently in a slightly different way that eliminates the need for a "target value":

**original problem **`P`

: Given an array `A`

of `n`

integers and a target value `S`

, does there exist a 3-tuple from `A`

that sums to `S`

?

**modified problem **`P'`

: Given an array `A`

of `n`

integers, does there exist a 3-tuple from `A`

that sums to zero?

Notice that you can go from this version of the problem `P'`

from `P`

by subtracting your S/3 from each element in `A`

, but now you don't need the target value anymore.

Clearly, if we simply test all possible 3-tuples, we'd solve the problem in O(n^{3}) -- that's the brute-force baseline. Is it possible to do better? What if we pick the tuples in a somewhat smarter way?

First, we invest some time to sort the array, which costs us an initial penalty of O(n log n). Now we execute this algorithm:

```
for (i in 1..n-2) {
j = i+1 // Start right after i.
k = n // Start at the end of the array.
while (k >= j) {
// We got a match! All done.
if (A[i] + A[j] + A[k] == 0) return (A[i], A[j], A[k])
// We didn't match. Let's try to get a little closer:
// If the sum was too big, decrement k.
// If the sum was too small, increment j.
(A[i] + A[j] + A[k] > 0) ? k-- : j++
}
// When the while-loop finishes, j and k have passed each other and there's
// no more useful combinations that we can try with this i.
}
```

This algorithm works by placing three pointers, `i`

, `j`

, and `k`

at various points in the array. `i`

starts off at the beginning and slowly works its way to the end. `k`

points to the very last element. `j`

points to where `i`

has started at. We iteratively try to sum the elements at their respective indices, and each time one of the following happens:

- The sum is exactly right! We've found the answer.
- The sum was too small. Move
`j`

closer to the end to select the next biggest number.
- The sum was too big. Move
`k`

closer to the beginning to select the next smallest number.

For each `i`

, the pointers of `j`

and `k`

will gradually get closer to each other. Eventually they will pass each other, and at that point we don't need to try anything else for that `i`

, since we'd be summing the same elements, just in a different order. After that point, we try the next `i`

and repeat.

Eventually, we'll either exhaust the useful possibilities, or we'll find the solution. You can see that this is O(n^{2}) since we execute the outer loop O(n) times and we execute the inner loop O(n) times. It's possible to do this sub-quadratically if you get really fancy, by representing each integer as a bit vector and performing a fast Fourier transform, but that's beyond the scope of this answer.

**Note:** Because this is an interview question, I've cheated a little bit here: this algorithm allows the selection of the same element multiple times. That is, (-1, -1, 2) would be a valid solution, as would (0, 0, 0). It also finds only the *exact* answers, not the closest answer, as the title mentions. As an exercise to the reader, I'll let you figure out how to make it work with distinct elements only (but it's a very simple change) and exact answers (which is also a simple change).

## Best Solution

Considering a set

`S`

of`N`

elements, and a given subset, each element either does or doesn't belong to that subset. Therefore are`2^N`

possible subsets (if you include the original and empty sets), and there is a direct mapping from the bits in the binary representation of`x`

between`0`

and`2^N`

to the elements in the`x`

th subset of`S`

.Once you've worked out how to enumerate the elements of a given subset, adding the values is simple.

For finding subsets which equal a total

`t`

for large`N`

, one optimisation might be to record those subsets which exceed`t`

, and not test any which are proper supersets of those. Testing whether set number`x`

is a superset of set`y`

can be achieved with a single bitwise operation and an integer comparison.