Problem Understanding

Given an array nums of n integers and a target sum target, the task is to find all unique quadruplets (a, b, c, d) such that a + b + c + d = target. It's crucial to return only distinct quadruplets, and the solution should not contains duplicate sets.

Example:

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

Algorithms

Brute Force Approach:

• Iterate over all possible quadruplets.
• Check if their sum equals the target.
• Avoid duplicates by maintaining a set of quadruplets.
• Complexity: O(n^4)

Optimized Two-Pointer Approach:

• Sort the array.
• Fix two elements and use two pointers to find the other two.
• Adjust pointers based on the comparison with the target.
• Complexity: O(n^3) due to sorting.

Hash Map Approach:

• Use a hash map to store the sum of pairs as keys and their indices as values.
• Iterate through all possible pairs, and check if the complement exists in the hash map.
• Complexity: O(n^2) with additional space for the hash map.