Python easy to understand ~25 lines - Dictionary - O(n^3)
\ntwo_sums = {}\nfor i in range(len(nums)):\n\tfor j in range(i + 1, len(nums)):\n\t\tif (target - nums[i] - nums[j]) in two_sums:\n\t\t\ttwo_sums[target - nums
```\ntwo_sums = {}\nfor i in range(len(nums)):\n\tfor j in range(i + 1, len(nums)):\n\t\tif (target - nums[i] - nums[j]) in two_sums:\n\t\t\ttwo_sums[target - nums[i] - nums[j]].append([i, j])\n\t\telse:\n\t\t\ttwo_sums[target - nums[i] - nums[j]] = [[i, j]]\n\nfour_sums = []\nfor i in range(len(nums)):\n\tfor j in range(i + 1, len(nums)):\n\t\ttemp = nums[i] + nums[j]\n\t\tif temp in two_sums:\n\t\t\tfor twos in two_sums[temp]:\n\t\t\t\tif not(twos[0] == i or\n\t\t\t\ttwos[0] == j or\n\t\t\t\ttwos[1] == i or\n\t\t\t\ttwos[1] == j):\n\t\t\t\t\tfour_sums.append([nums[i], nums[j], nums[twos[0]], nums[twos[1]]])\n\nreturn sorted(list(set(map(lambda x: tuple(sorted(x)), four_sums))))\n```\n\n* Highly suggest you solve [Two Sum](https://leetcode.com/problems/two-sum/) and maybe even [3Sum](https://leetcode.com/problems/3sum/) first\n* How do you break up a 4Sum problem?\n\t* A simple approach is to find a pair of numbers first\n\t* Then find another pair such that the set of those 4 numbers adds up to `target`\n\n\n* First dictionary iterates through the array and adds all `i, j` pairs to a dictionary\n* Key in this case will be `target - nums[i] - nums[j]`\n\t* Why `target - nums[i] - nums[j]`? `target` in the first example in the code desc. is 0. `i - j` for say, 3rd (i) and 2nd (j) index is 1\n\t* Essentially, this is `target` *without* `nums[i]` and `nums[j]` i.e the number your second pair that you find later needs to add up to\n\t* This is because you have *removed* `nums[i]` and `nums[j]` from target\n\t* In a nutshell, you say that an entry `x` in your dictionary represents how much of `target` you need to find if you take an entry `i, j` from the list that is held in that entry\'s value\n\n* After you build the dictionary, iterate through the array of numbers\n* For each number, iterate through each number *after* it in the array (O(n^2))\n* Add those two numbers up\n\t* See a pattern here? If the sum of these two numbers is in the dictionary we built, you know every permutation of two *other* numbers in the array that give you `target` when you add them up\n\t* Look at every pair of those and ignore pairs where one of the indices is the same\n\t\t* If the index is the same, you are looking at the same element. You need 4 different elements to add up to `target`\n\t* Record all quadruplets this way\n\n\n* Sort quadruplets and then sort the list of quadruplets\n* Why do I have so many calls in the last line?\n\t* From right to left:\n\t\t* `sorted(x)` sorts the quadruplet\n\t\t* `tuple(sorted(x))` converts the sorted quadruplet into a tuple so it\'s hashable\n\t\t* `map` this for every element in `four_sums` i.e every quadruplet\n\t\t* Convert the list of quadruplets into a `set` so you only have unique elements\n\t\t\t* This is why we had to `tuple`-fy every quadruplet - so we can hash it\n\t\t* Convert said set of quadruplets into a `sorted` `list`\n* Ta-da!
['Python3']