LC18 4Sum

class Solution:
    """
        main idea: for sorted arr, convert general N sum to two pointers + backtracking;
        base case: two sum, termination condition: check if arr[l] + arr[r] == target   arr size == 2  ; general case: N sum 
    
    """
# time O(N^3) space O(N) 
# main idea: use l,r pointers to find valid unique combination(backtracking) in sorted nums; 
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        if not nums or len(nums)< 4:
            return []
        nums.sort()

        res = []
        self.findNsum(nums,target,4,[],res)
        return res
    def findNsum(self,arr,target,N,path,res):
        if len(arr) < N or N < 2:return 
        if N == 2:
            l,r = 0,len(arr)-1
            while l < r:
                if arr[l] + arr[r] == target:
                    res.append(path+[arr[l],arr[r]])
                    l += 1
                    r -= 1
                    while l < r and arr[l]==arr[l-1]:
                        l += 1
                    while l < r and arr[r] == arr[r+1]:
                        r -= 1
                elif arr[l] + arr[r] < target:
                    l += 1
                else:
                    r -= 1
        else:
            for i in range(0,len(arr)-N+1):
                if target < arr[i]*N or target > arr[-1]*N:
                    break
                if i == 0 or (i > 0 and arr[i] != arr[i-1]):
                    self.findNsum(arr[i+1:],target-arr[i],N-1, path+[arr[i]],res)
        return 

class Solution:
        def fourSum(self, A, target):
            """ tc O(NlgN + N^(K-1)) sc O(K)
            """
            def backtrack( l, r, K, path, target, res):
                # early termination
                if r - l + 1  < K  or K < 2 or  A[l]*K > target or A[r]*K < target: 
                    return  
                if K == 2: # two pointers solve sorted 2-sum problem
                    while l < r:
                        twoSum = A[l] + A[r] 
                        if twoSum == target:
                            res.append(path + [A[l], A[r]]) # backtrack 

                            l += 1 
                            while l < r and A[l] == A[l-1]:
                                l += 1 
                        elif twoSum < target:
                            l += 1
                        else:
                            r -= 1 
                else:# recursively reduce K
                    for i in range(l,r+1):#range(len(A)-K-1):
                        if i == l or (i > l and A[i] != A[i-1]):
                            backtrack(i+1, r, K-1, path+[A[i]], target-A[i], res)
                
                
            res = [] 
            A.sort()
            backtrack(0, len(A)-1, 4, [], target, res)
            return res