四数相加到 k 数相加（k sum）

归降级为解决两数相加

class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        nums.sort()
        return self.k_sum(nums, target, 4, 0)

    def twoSum(self, nums, target, index = 0):
        # print('twoSum, target, index:', target, index)
        # nums.sort()
        l = len(nums) - index
        if l <= 1:
            return []
        left = index
        right = l - 1 + index
        result = []
        while left < right:
            tmp = nums[left] + nums[right]
            if tmp > target:
                if left + 1 < right and nums[left] + nums[left + 1] > target:
                    break
                right -= 1
            elif tmp < target:
                if right - 1 > left and nums[right - 1] + nums[right] < target:
                    break
                left += 1
            else:
                if not (left > 0 + index and nums[left - 1] == nums[left]):
                    r = [nums[left], nums[right]]
                    result.append(r)
                right -= 1
                left += 1
        # ultra_result = result[0] if len(result) > 0 else []
        return result
    
    def k_sum(self, nums, default_target = 0, k = 3, index = 0):
        # assuming that he left most one of the three answer items is fixed
        # nums.sort()
        # print('k, default_target, index:', k, default_target, index)
        result = []
        l = len(nums) - index
        if l <= k - 1:
            return result
        for i in range(index, l + index):
            target = default_target - nums[i]
            # print('k, index, i, target:', k, index, i, target, nums[i+1:])
            if i > 0 + index and nums[i] == nums[i - 1]:
                # remove duplicate items
                continue
            if k <= 3:
                r = self.twoSum(nums, target, i + 1)
            else:
                r = self.k_sum(nums, target, k - 1, i + 1)

            for item in r:
                item.append(nums[i])
                item.sort()
            # print('r:', r)
            result.extend(r)
        return result