Problem statement

https://leetcode.com/problems/4sum/

Solution

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.

So, 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.

Complexity

We 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.

Code

class Solution:
    def fourSum(self, nums, target):
        nums.sort()
        n, ans = len(nums), []
        for i in range(n):
            for j in range(i + 1, n):
                goal = target - nums[i] - nums[j]
                beg, end = j + 1, n - 1

                while beg < end:
                    if nums[beg] + nums[end] < goal:
                        beg += 1
                    elif nums[beg] + nums[end] > goal:
                        end -= 1
                    else:
                        ans.append((nums[i], nums[j], nums[beg], nums[end]))
                        beg += 1
                        end -= 1

        return set(ans)