4sum

Intuition

The goal is to find all unique quadruplets in the array that add up to a target sum. Since this is an extension of the 3Sum problem, we can apply a similar approach by breaking down the problem. Specifically, we can use a helper function (threeSum) to handle three of the numbers, and then combine it with a fourth number in the main function.

Approach

Below is the step-by-step breakdown of the approach:

1. Sort the Array:
   • Sorting helps eliminate duplicates and allows us to use a two-pointer approach efficiently.
2. Iterate with a Fixed Element and Apply threeSum:
   • For each index i in the array:
     • Use the threeSum function to find combinations of three other elements in the subarray (starting from i+1) that, along with nums[i], sum to the target.
     • Skip duplicates to ensure unique quadruplets.
   • Helper Function threeSum:
     • This function applies the two-pointer technique to find triplets within the sorted subarray that add up to a given target.
3. Return the Result:
   • The final list of unique quadruplets is returned after all possibilities are explored.

Complexity

• Time complexity: $O(n^3)$, as the fourSum function iterates through the array and calls the threeSum function, which itself uses a two-pointer approach.
• Space complexity: $O(n)$, for storing results and handling recursion.

Code

function threeSum(nums: number[], target: number, start: number): number[][] {
  const results: number[][] = []
  for (let left = start; left < nums.length - 2; left++) {
    if (left > start && nums[left] === nums[left - 1]) continue
    let middle = left + 1
    let right = nums.length - 1
    while (middle < right) {
      const sum = nums[left] + nums[middle] + nums[right]
      if (sum === target) {
        results.push([nums[left], nums[middle], nums[right]])
        while (middle < right && nums[middle] === nums[middle + 1]) middle++
        while (middle < right && nums[right] === nums[right - 1]) right--
        middle++
        right--
      } else if (sum > target) {
        right--
      } else {
        middle++
      }
    }
  }
  return results
}
 
function fourSum(nums: number[], target: number): number[][] {
  nums = nums.sort((a, b) => a - b)
  const results: number[][] = []
  for (let i = 0; i < nums.length - 3; i++) {
    if (i > 0 && nums[i] === nums[i - 1]) continue
    const list = threeSum(nums, target - nums[i], i + 1)
    for (const triplet of list) {
      results.push([nums[i], …triplet])
    }
  }
  return results
}