Python 140ms beats 100%, and works for N-sum (N>=2)
The core is to implement a fast 2-pointer to solve 2-sum, and recursion to reduce the N-sum to 2-sum. Some optimization was be made knowing the list is sorted.\
The core is to implement a fast 2-pointer to solve 2-sum, and recursion to reduce the N-sum to 2-sum. Some optimization was be made knowing the list is sorted.\n\n    def fourSum(self, nums, target):\n        nums.sort()\n        results = []\n        self.findNsum(nums, target, 4, [], results)\n        return results\n    \n    def findNsum(self, nums, target, N, result, results):\n        if len(nums) < N or N < 2: return\n    \n        # solve 2-sum\n        if N == 2:\n            l,r = 0,len(nums)-1\n            while l < r:\n                if nums[l] + nums[r] == target:\n                    results.append(result + [nums[l], nums[r]])\n                    l += 1\n                    r -= 1\n                    while l < r and nums[l] == nums[l - 1]:\n                        l += 1\n                    while r > l and nums[r] == nums[r + 1]:\n                        r -= 1\n                elif nums[l] + nums[r] < target:\n                    l += 1\n                else:\n                    r -= 1\n        else:\n            for i in range(0, len(nums)-N+1):   # careful about range\n                if target < nums[i]*N or target > nums[-1]*N:  # take advantages of sorted list\n                    break\n                if i == 0 or i > 0 and nums[i-1] != nums[i]:  # recursively reduce N\n                    self.findNsum(nums[i+1:], target-nums[i], N-1, result+[nums[i]], results)\n        return\n\n\nJust revisited and clean the code\n\n\n    def fourSum(self, nums, target):\n        def findNsum(nums, target, N, result, results):\n            if len(nums) < N or N < 2 or target < nums[0]*N or target > nums[-1]*N:  # early termination\n                return\n            if N == 2: # two pointers solve sorted 2-sum problem\n                l,r = 0,len(nums)-1\n                while l < r:\n                    s = nums[l] + nums[r]\n                    if s == target:\n                        results.append(result + [nums[l], nums[r]])\n                        l += 1\n                        while l < r and nums[l] == nums[l-1]:\n                            l += 1\n                    elif s < target:\n                        l += 1\n                    else:\n                        r -= 1\n            else: # recursively reduce N\n                for i in range(len(nums)-N+1):\n                    if i == 0 or (i > 0 and nums[i-1] != nums[i]):\n                        findNsum(nums[i+1:], target-nums[i], N-1, result+[nums[i]], results)\n\n        results = []\n        findNsum(sorted(nums), target, 4, [], results)\n        return results\n\t\t\t\t\npassing pointers, not sliced list\n\n    def fourSum(self, nums, target):\n        def findNsum(l, r, target, N, result, results):\n            if r-l+1 < N or N < 2 or target < nums[l]*N or target > nums[r]*N:  # early termination\n                return\n            if N == 2: # two pointers solve sorted 2-sum problem\n                while l < r:\n                    s = nums[l] + nums[r]\n                    if s == target:\n                        results.append(result + [nums[l], nums[r]])\n                        l += 1\n                        while l < r and nums[l] == nums[l-1]:\n                            l += 1\n                    elif s < target:\n                        l += 1\n                    else:\n                        r -= 1\n            else: # recursively reduce N\n                for i in range(l, r+1):\n                    if i == l or (i > l and nums[i-1] != nums[i]):\n                        findNsum(i+1, r, target-nums[i], N-1, result+[nums[i]], results)\n\n        nums.sort()\n        results = []\n        findNsum(0, len(nums)-1, target, 4, [], results)\n        return results
['Python']