18. 4Sum

https://leetcode.com/problems/4sum/
经典，就算看过多少遍，还是那么难写出来。

个人解答

class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        nums.sort()
        def kSum(a, k, t):
            res = []
            if k == 2:
                # 2-sum
                l, r = 0, len(a) - 1
                while l < r:
                    s = a[l] + a[r]
                    if s == t:
                        res.append([a[l], a[r]])
                        l += 1
                        r -= 1
                        while l < len(a) and a[l] == a[l - 1]:
                            l += 1
                        while r >= 0 and a[r] == a[r + 1]:
                            r -= 1
                    elif s < t:
                        l += 1
                        while l < len(a) and a[l] == a[l - 1]:
                            l += 1
                    else:
                        r -= 1
                        while r >= 0 and a[r] == a[r + 1]:
                            r -= 1                        
            else:
                for i in range(0, len(a) - k + 1):
                    if i > 0 and a[i] == a[i - 1]:
                        continue
                    ret = kSum(a[i + 1:], k - 1, t - a[i])
                    res += [[a[i]] + l for l in ret]
            return res
        return kSum(nums, 4, target)

题目分析

对于K-sum，归约成K-1 sum
到最后，变成2-sum

需要考虑重复的情况