<gh_stars>0
"""
18
4sum
medium

Given an array nums of n integers, return an array of all the
unique quadruplets [nums[a], nums[b], nums[c], nums[d]] such that:

0 <= a, b, c, d < n
a, b, c, and d are distinct.
nums[a] + nums[b] + nums[c] + nums[d] == target
You may return the answer in any order.
"""

from typing import List

class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:

        if len(nums) < 4:
            return []

        res = []
        pairs = {}

        def find(i, j):
            if (i, j) in pairs:
                return
            else:
                pairs[(i,j)] = None
            if i < j-2:
                lo = nums[i] + nums[j] + nums[i+1] + nums[i+2]
                hi = nums[i] + nums[j] + nums[j-1] + nums[j-2]
                if lo > target or hi < target:
                    find(i+1, j)
                    find(i, j-1)
                    return

                m = i + 1
                n = j - 1
                while m < n:
                    tol = nums[i] + nums[j] + nums[m] + nums[n]
                    if tol == target:
                        if sorted([nums[i], nums[j], nums[m], nums[n]]) not in res:
                            res.append(sorted([nums[i], nums[j], nums[m], nums[n]]))
                        m += 1
                    elif tol > target:
                        n -= 1
                    else:
                        m += 1
                find(i+1, j)
                find(i, j-1)

        nums.sort()
        find(0, len(nums)-1)

        return res


nums = [-493,-482,-482,-456,-427,-405,-392,-385,-351,-269,-259,-251,-235,-235,-202,-201,-194,-189,-187,-186,-180,-177,-175,-156,-150,-147,-140,-122,-112,-112,-105,-98,-49,-38,-35,-34,-18,20,52,53,57,76,124,126,128,132,142,147,157,180,207,227,274,296,311,334,336,337,339,349,354,363,372,378,383,413,431,471,474,481,492]

target = 6189

sol = Solution()
print(sol.fourSum(nums, target))


"""
18
4sum
medium

Given an array nums of n integers, return an array of all the
unique quadruplets [nums[a], nums[b], nums[c], nums[d]] such that:

0 <= a, b, c, d < n
a, b, c, and d are distinct.
nums[a] + nums[b] + nums[c] + nums[d] == target
You may return the answer in any order.
"""

from typing import List

class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:

        if len(nums) < 4:
            return []

        res = []
        pairs = {}

        def find(i, j):
            if (i, j) in pairs:
                return
            else:
                pairs[(i,j)] = None
            if i < j-2:
                lo = nums[i] + nums[j] + nums[i+1] + nums[i+2]
                hi = nums[i] + nums[j] + nums[j-1] + nums[j-2]
                if lo > target or hi < target:
                    find(i+1, j)
                    find(i, j-1)
                    return

                m = i + 1
                n = j - 1
                while m < n:
                    tol = nums[i] + nums[j] + nums[m] + nums[n]
                    if tol == target:
                        if sorted([nums[i], nums[j], nums[m], nums[n]]) not in res:
                            res.append(sorted([nums[i], nums[j], nums[m], nums[n]]))
                        m += 1
                    elif tol > target:
                        n -= 1
                    else:
                        m += 1
                find(i+1, j)
                find(i, j-1)

        nums.sort()
        find(0, len(nums)-1)

        return res


nums = [-493,-482,-482,-456,-427,-405,-392,-385,-351,-269,-259,-251,-235,-235,-202,-201,-194,-189,-187,-186,-180,-177,-175,-156,-150,-147,-140,-122,-112,-112,-105,-98,-49,-38,-35,-34,-18,20,52,53,57,76,124,126,128,132,142,147,157,180,207,227,274,296,311,334,336,337,339,349,354,363,372,378,383,413,431,471,474,481,492]

target = 6189

sol = Solution()
print(sol.fourSum(nums, target))
18 4sum medium  Given an array nums of n integers, return an array of all the unique quadruplets [nums[a], nums[b], nums[c], nums[d]] such that:  0 <= a, b, c, d < n a, b, c, and d are distinct. nums[a] + nums[b] + nums[c] + nums[d] == target You may return the answer in any order.