LeetCode problem #18–4Sum(JavaScript)

In this LeetCode challenge, we’re asked to build a function that takes an array of numbers, and finds all combinations of 4 numbers that add up to make a specified target.

The problem is basically a slightly more complex version of the 3 sum problem, and so it carries a near identical solution. The change is that we wrap the 3 sum solution in an additional for loop, in order to cover all possible combinations.

Solution: Contracting window

We start by looping through the sorted array of numbers, excluding the final 3 (as we need 4 elements to add together). For each number, we then loop through the remaining elements (excluding the final 2, as we now need 3 numbers). What we have left, is a series of numbers that can make up the 3rd and 4th number in the equation, so here is where we establish our contracting window. Our window’s left-hand side goes immediately after the inner loop’s number, and out right-hand side goes to the end of the array. We then sum together the 4 chosen numbers.

If the sum of all 4 numbers matches our target, we add this combination of numbers to a list of potential solutions, and then we contract the window on both sides (as contracting on one side couldn’t possibly give us another solution).

If the sum is below our target, then we move the left-hand side of the window inwards until we reach a different number. Likewise, if the sum is above our target, we move the right-hand side of the window inwards until we reach a different number. Then, the check is performed again.