0018: 4Sum

Problem Statement

Given an array nums of n integers, return an array of all the unique quadruplets [nums[a], nums[b], nums[c], nums[d]] such that:

  • 0 <= a, b, c, d < n
  • a, b, c, and d are distinct.
  • nums[a] + nums[b] + nums[c] + nums[d] == target

You may return the answer in any order.

Example 1:

Input: nums = [1,0,-1,0,-2,2], target = 0
Output: [[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]

Example 2:

Input: nums = [2,2,2,2,2], target = 8
Output: [[2,2,2,2]]

Constraints:

  • 1 <= nums.length <= 200
  • -109 <= nums[i] <= 109
  • -109 <= target <= 109

Code Solution

class Solution:
    def fourSum(self, nums, target):
	    N = len(nums)
	    
        if N < 4:
            return []
	    
        nums.sort()
        
        result = []
        for x1 in range(0, N, 1):    
            if x1 > 0 and nums[x1 - 1] == nums[x1]:
                continue
            for x2 in range(1 + x1, N, 1):                
                if x2 > 1 + x1 and nums[x2 - 1] == nums[x2]:
                    continue
	                
                x3 = x2 + 1
                x4 = N - 1
                while x3 < x4:
                    S = nums[x1] + nums[x2] + nums[x3] + nums[x4]
                    if S < target:
                        x3 = x3 + 1
                    elif S > target:
                        x4 = x4 - 1
                    else:
                        result.append([nums[x1], nums[x2], nums[x3], nums[x4]])
                        while x3 < x4 and nums[x3] == nums[1 + x3]:
                            x3 = x3 + 1
                        x3 = x3 + 1                        
        return result