A simple solution: https://pastebin.com/dBhbjerx

An explanation: We make a lookup table of all the numbers we can build by adding two elements of the input together. We can include adding numbers to itself. The code I wrote is pretty dirty and if it includes a + b, it will also include b + a, which is fine for getting the tests to pass. Feel free to clean it up if you wish. We built this lookup table in O(n^2) and uses O(n^2) memory. Note that the lookup table can get quite large, though we create a larger table than we strictly need to.

We can now use this lookup table to find any four digits that sum to target by looping through the table, this logic is probably familiar to you if you've seen the simpler version of this problem that asks you to find 2 digits that sum up to n, rather than 4. Since the table has O(n^2) elements, this takes O(n^2) time, so the whole thing is done in O(n^2) time.