Leet Code 4Sum Solution: https://leetcode.com/problems/4sum/

4Sum.py

class Solution:
  """
  Solution to Leet Code problem 4Sum: https://leetcode.com/problems/4sum/ 
  Runtime: 100 ms beats 93.4% of python3 submissions
  """
  def fourSum(self, nums, target):
    """
    :type nums: List[int]
    :type target: int
    :rtype: List[List[int]]
    """
    # Edge cases:
    if len(nums) < 4:
        return []
    if 4 * max(nums) < target:
        return []
    
    nums = sorted(nums)
    n = len(nums)
    solutions = set()
    for _a in range(n - 3):
        ta = target - nums[_a]
        for _d in range(_a + 3, n):
            tad = ta - nums[_d]
            # Skip the following cases:
            if nums[_d - 2] + nums[_d - 1] < tad:
                continue
            if nums[_a + 1] + nums[_a + 2] > tad:
                continue
            _b, _c = _a + 1, _d - 1
            while _b < _c:
                b, c = nums[_b], nums[_c]
                bc = b + c
                if bc == tad:
                    a, d = nums[_a], nums[_d]
                    solutions.add((a, b, c, d))
                    _b += 1
                elif bc > tad: # decrease c to make bc closer to tad
                    _c -= 1
                else: # increase b to make bc closer to tad
                    _b += 1
    return list(solutions)