[Python] O(n^3) and why we can not do better, explained
In this problem we are asked to find not one 4-sum with sum equal to target, but all of them. If we were asked to find only one sum, there is O(n^2) solution: c
In this problem we are asked to find not one 4-sum with sum equal to `target`, but all of them. If we were asked to find only one sum, there is `O(n^2)` solution: create array of pairs and then try to find the new pair is equal to `target` minus sums of two numbers. However we need to return all sums and imagine the case `nums = [1, 2, 3, ..., n]`. Then there will be `C_n^4 = O(n^4)` different ways to choose `4` number out of `n` and all sums are in range `[4, 4n]`. It means, that by pingenhole principle there will be some sum which we meet `Omega(n^3)` times, that is `>= alpha*n^3` for some constant alpha.\n\nSo, in general case we can have only `O(n^3)` solution (though with small constant, like 1/6) which allows us to pass problem constraints. The idea is exaclty the same as in other **2Sum** problems: sort numbers, choose `i` and `j` and then use two pointers approach to get solutions.\n\n#### Complexity\nWe need to choose `i` and `j` with complexity `O(n^2)` and then for each choosen pair use two-pointers approach so we have `O(n^3)` total complexity. Space complexity is `O(n)` to keep sorted data.\n\n#### Code\n```python\nclass Solution:\n    def fourSum(self, nums, target):\n        nums.sort()\n        n, ans = len(nums), []\n        for i in range(n):\n            for j in range(i + 1, n):\n                goal = target - nums[i] - nums[j]\n                beg, end = j + 1, n - 1\n\n                while beg < end:\n                    if nums[beg] + nums[end] < goal:\n                        beg += 1\n                    elif nums[beg] + nums[end] > goal:\n                        end -= 1\n                    else:\n                        ans.append((nums[i], nums[j], nums[beg], nums[end]))\n                        beg += 1\n                        end -= 1\n\n        return set(ans)\n```\n\nIf you have any questions, feel free to ask. If you like solution and explanations, please **Upvote!**
[]