Python Recursive solution with O(n^3), highly readable


  • 1

    The key technique in this problem is to use recursion to break it into sub problems.

    class Solution(object):
      # Recursive solution based on two sum (Improved version)
      def twoSum(self, nums, target):
        results = []
        l, r = 0, len(nums) -1
        while l < r:
          s = nums[l] + nums[r]
          if s == target:
            results.append([nums[l], nums[r]])
            while l < r and nums[l] == nums[l+1]: l += 1
            while l < r and nums[r] == nums[r-1]: r -= 1
            l += 1; r -=1
          elif s < target:
            l += 1
          else:
            r -= 1
        return results
    
      def nSum(self, N, nums, target):
        if N == 2:
          return self.twoSum(nums, target)
        results = []
        for i in range(len(nums)-(N-1)):
          if i == 0 or nums[i] != nums[i-1]:
            tmp = self.nSum(N-1, nums[i+1:], target-nums[i])
            for t in tmp:
              results.append([nums[i]]+t)
        return results
    
      def fourSum(self, nums, target):
        nums.sort()
        return self.nSum(4, nums, target)
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.