18. 4sum

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.

solution

It’s basically the same as 15-3sum, but we have two nested loops for the first two values, giving us a runtime of $O(n^3)$.

def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
	n = len(nums)
	nums.sort()
 
	ans = set()
 
	# try first number
	for i in range(n-3):
		# try second number
		for j in range(i+1,n-2):
			goal = target - nums[i] - nums[j]
			l, r = j+1, n-1
			while l < r:
				val = nums[l] + nums[r]
				if val == goal:
					ans.add((nums[i],nums[j],nums[l],nums[r]))
					l += 1
					r -= 1
				elif val < goal:
					l += 1
				else:
					r -= 1
	return list(ans)