Python3 | Brute-force > Better > Optimal | Full Explanation
Approach\n    - Brute-force\n        - We keep four-pointers i, j, k and l. For every quadruplet, we find the sum of A[i]+A[j]+A[k]+A[l]\n        - If this sum 
- Approach\n    - Brute-force\n        - We keep four-pointers `i`, `j`, `k` and `l`. For every quadruplet, we find the sum of `A[i]+A[j]+A[k]+A[l]`\n        - If this sum equals the target, we\u2019ve found one of the quadruplets and add it to our data structure and continue with the rest\n        - Time Complexity: $O(n^4)$\n        - Space Complexity: $O(m)$ where m is the number of quadruplets\n    - Better\n        - We store the frequency of each element in a HashMap\n        - Based on `a + b + c + d = target` we can say that `d = target - (a+b+c)` and based on this we fix 3 elements `a`, `b` and `c` and try to find the `-(a+b+c)` in HashMap\n        - Time Complexity: $O(n^3)$\n        - Space Complexity: $O(n + m)$ where m is the number of quadruplets\n    - Optimal\n        - To get the quadruplets in sorted order, we will sort the entire array in the first step and to get the unique quads, we will simply skip the duplicate numbers while moving the pointers\n        - Fix 2 pointers `i` and `j` and move 2 pointers `lo` and `hi`\n        - Based on `a + b + c + d = target` we can say that `c + d = target - (a+b)` and based on this we fix element as `a` and `b` then find `c` and `d` using two pointers `lo` and `hi` (same as in 3Sum Problem)\n        - Time Complexity: $O(n^3)$\n        - Space Complexity: $O(m)$ where m is the number of quadruplets\n\n```python\n# Python3\n# Brute-force Solution\nclass Solution:\n    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:\n        n = len(nums)\n        ans = set()\n        for i in range(n-3):\n            for j in range(i+1, n-2):\n                for k in range(j+1, n-1):\n                    for l in range(k+1, n):\n                        if nums[i] + nums[j] + nums[k] + nums[l] == target:\n                            ans.add(tuple(sorted((nums[i], nums[j], nums[k], nums[l]))))\n        \n        res = []\n        for i in ans:\n            res += list(i),\n        return res\n```\n\n```python\n# Python3\n# Better Solution\nfrom collections import defaultdict\nclass Solution:\n    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:\n        n = len(nums)\n        ans = set()\n        hmap = defaultdict(int)\n        for i in nums:\n            hmap[i] += 1\n        \n        for i in range(n-3):\n            hmap[nums[i]] -= 1\n            for j in range(i+1, n-2):\n                hmap[nums[j]] -= 1\n                for k in range(j+1, n-1):\n                    hmap[nums[k]] -= 1\n                    rem = target-(nums[i] + nums[j] + nums[k])\n                    if rem in hmap and hmap[rem] > 0:\n                        ans.add(tuple(sorted((nums[i], nums[j], nums[k], rem))))\n                    hmap[nums[k]] += 1\n                hmap[nums[j]] += 1\n            hmap[nums[i]] += 1\n        \n        res = []\n        for i in ans:\n            res += list(i),\n        return res\n```\n\n```python\n# Python3\n# Optimal Solution\nclass Solution:\n    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:\n        n = len(nums)\n        nums.sort()\n        res = []\n\n        for i in range(n-3):\n            # avoid the duplicates while moving i\n            if i > 0 and nums[i] == nums[i - 1]:\n                continue\n            for j in range(i+1, n-2):\n                # avoid the duplicates while moving j\n                if j > i + 1 and nums[j] == nums[j - 1]:\n                    continue\n                lo = j + 1\n                hi = n - 1\n                while lo < hi:\n                    temp = nums[i] + nums[j] + nums[lo] + nums[hi]\n                    if temp == target:\n                        res += [nums[i], nums[j], nums[lo], nums[hi]],\n\n                        # skip duplicates\n                        while lo < hi and nums[lo] == nums[lo + 1]:\n                            lo += 1\n                        lo += 1\n                        while lo < hi and nums[hi] == nums[hi - 1]:\n                            hi -= 1\n                        hi -= 1\n                    elif temp < target:\n                        lo += 1\n                    else:\n                        hi -= 1\n        return res\n```
['Array', 'Hash Table', 'Two Pointers', 'Sorting', 'Python3']