[Java] Threesums, find all triples from given set of numbers that sum up to a given target

Finally a clickbait-worthy exercise :)

Given a set of integers and a target K, find all distinct triples that sum up to K.

Two triples are distinct if their content is different, order does not matter, eg: 1, 2, 2 and 2, 2, 1 are the same triple.

A first approach might be to explore all possible combinations and keep creating tuples then triples and verify which ones respect the a+b+c = K condition.

We can use a queue and add elements to it until we have formed a triple, each time expanding the given input by one valid element only (therefore ignoring elements we already used).

This can also be done with a triple nested loop, but the complexity is in the O(N^3) time.

We've already seen a way of finding a couple of elements that sum of to K in linear time, but that solution stops after it finds the first valid result. We could adapt it to keep iterating until all elements are checked to gather all valid results still in O(N) time and space.

That solution, executed N times for each element in our input would give us a O(N^2) runtime since for each element in input we just need to test whether the found pair completes the equation. We might need to handle duplicates, maybe using a set and a dedicated Triple class with a relevant equals method, but nothing major.

Another possibility however is to process the given input a bit and sort it, this then allows running a linear search similar to our pair problem which yields all couple of elements that summed up to the current element reach our target. The upside of this approach is that we use no extra space, the downside is that we need to sort the input. Therefore it is worth doing for this specific case where we're looking for a triple, but not worth for the other problem since the cost of sorting is higher than the single walk on the input.

The idea is: given an element in the sorted array, consider the rest of the array as our search space from the next element until the end.

We then verify whether the elements pointed at by the extremes of our search window complement us in reaching the target, we can have three cases:

• all elements reach the target: this is a valid solution, track it AND continue our search since we might have more pairs that satisfy our condition
• the sum of all element is bigger than the target. We therefore need to decrease this sum to get closer to our target. Since the array is sorted, shrinking our search window from the end must make us encounter a lower value
• the sum of all element is lower than the target. Similar to the previous case but we shrink the window from the start instead since we're looking for bigger values

While doing this, we can skip duplicate elements and check our boundaries carefully to reach our solution.

You can check my implementation of threeSums on my Gist along with some test cases in ThreeSumsJTests.