h2. 4sum

bq. Given an array of integers, find out if there are any four numbers such that the sum of the first three equal to the fourth (you can use the same number more than once).

bq. Given an array of integers, find out if there are any four numbers such that their sum equals zero. For example ... (you can use the same number more than once).

The naive algorithm is $O(N^4^)$ try all the possible combinations of four numbers.
A less naive algorithm brute forces through all $n^3^$ combinations of three numbers and then efficiently checks if their sum is in the original array using a hash table. This algorithm has $O(n^3^)$ complexity.

By now, you’ve probably started thinking how meet in the middle can be applied to this problem. The trick is to rewrite the equation as $a + b = d - c$. Store all the $n^2^$ sums $a + b$ in a hash set $S$. Then iterate through all $n^2^$ combinations for c and d and check if $S$ contains $d - c$.

By now, you’ve probably started thinking how meet in the middle can be applied to this problem. The trick is to rewrite the equation as $a + b = -(c + d)$. Store all the $n^2^$ sums $a + b$ in a hash set $S$. Then iterate through all $n^2^$ combinations for c and d and check if $S$ contains $-(c + d)$.

Here's how the code looks
== code(c) |
def 4sum(A):

  sums = {}

  S = {}

  for a in A:
    for b in A:

      sums[a + b] = (a, b)

      S[a + b] = (a, b)
 

  for c in A:
    for d in A:
      if -(c + d) in sums:

        print (sums[-(c + d)][0], sums[-(c + d)][1], c, d)
      return

        print (S[-(c + d)][0], S[-(c + d)][1], c, d)
        return

==
This algorithm has $O(n^2^)$ time and space complexity.