# time: O(n ** 3)

class Solution:
    ELEMENTS_COUNT = 4

    def four_way(self, nums, target):
        results = []
        self.n_way(sorted(nums), target, [], self.ELEMENTS_COUNT, results)
        return results
    
    def n_way(self, nums, target, partial, n, results):
        if len(nums) < n or nums[0] * n > target or nums[-1] * n < target:
            return
        
        if n == 2:
            left, right = 0, len(nums)
            while left < right:
                if nums[left] + nums[right] == target:
                    results.append(partial + [nums[left], nums[right]])
                    left += 1
                    right -= 1
                    while nums[right] == nums[right + 1] and right > left:
                        right -= 1
                    while nums[left] == nums[left - 1] and left < right:
                        left += 1
                elif nums[left] + nums[right] < target:
                    left += 1
                else:
                    right -= 1
        else:
            # add the next element in the list to partial, in order to get to 2-sum
            for i in range(len(nums) - n + 1):
                if i == 0 or nums[i] != nums[i - 1]: # avoid dups if possible
                    self.n_way(nums[i + 1 :], target - nums[i], partial + [nums[i]], n - 1, results)