Foursum

4sum.py

# This is one way
class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        nums.sort()
        result = []
        for idx, num in enumerate(nums):
            for res3list in self.threeSum(nums[idx+1:], target-num):
                if [num] + res3list not in result:
                    result += [[num] + res3list]
        return result


    def threeSum(self, nums: List[int], target: int) -> List[int]:
        result = []
        for idx, num in enumerate(nums):
            for res2list in self.twoSum(nums[idx+1:], target-num):
                if [num] + res2list not in result:
                    result += [[num] + res2list]
        return result
    
    def twoSum(self, nums:List[int], target: int) -> List[int]:
        left, right = 0, len(nums)-1
        res = []
        while left < right:
            result = nums[left] + nums[right]
            # print("left, right, result=", left, right, result, target)
            if result == target:
                res += [[nums[left], nums[right]]]
                left += 1
                right -= 1
            elif result < target:
                left += 1
            else:
                right -= 1
        return res

# So is this for 5sum, 6sum, 10000sum with O(N^(ksum-1)) runtime
class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        nums.sort()
        result = []
        for idx, num in enumerate(nums):
            for res3list in self.nSum(nums[idx+1:], target-num, 3):
                if [num] + res3list not in result:
                    result += [[num] + res3list]
        return result

    
    def nSum(self, nums: List[int], target: int, n: int) -> List[int]:
        match n - 1:
            case 2:
                fn = self.twoSum
            case _:
                fn = self.nSum
        result = []
        for idx, num in enumerate(nums):
            for reslist in fn(nums[idx+1:], target-num, n-1):
                if [num] + reslist not in result:
                    result += [[num] + reslist]
        return result
    
    def twoSum(self, nums:List[int], target: int, _n: int) -> List[int]:
        left, right = 0, len(nums)-1
        res = []
        while left < right:
            result = nums[left] + nums[right]
            # print("left, right, result=", left, right, result, target)
            if result == target:
                res += [[nums[left], nums[right]]]
                left += 1
                right -= 1
            elif result < target:
                left += 1
            else:
                right -= 1
        return res