The question

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
• -10⁹ <= nums[i] <= 10⁹
• -10⁹ <= target <= 10⁹

The concept of solution

The easiest solution happens to be the most optimal one here. Intuitively the we have to check almost every combination of numbers. The brute force way of simply creating 4 loops is fine but could be improved. Instead of 4 loops, let’s do 2 loops, they provide us with the initial combination of [a, b, x₁, x₂]. The last two numbers could be found in a smarter way. Instead doing 2N (going through the list twice), we could use two pointers. One at the start, one at the end. At this stage we are not looking for a " target"but for “target - a - b”. Hence, two pointers should provide us with a pair of numbers that add up to “target - a - b - x₁ - x₂ = 0”. The algorithm for finding the two numbers would be simply something along the lines of:

	# There is an offset of already selected values in loops
	left = 2
	right = nums.length
	while(left < right):
		if(nums[left] + nums[right] > target - a -b):
			right -= 1
		elif(nums[left] + nums[right] < target - a -b):
			left += 1
		else:
			return (nums[left], nums[right])
	return (-1, -1)

Key takeaways

• Pointers in array questions are an often sighting, be aware