Find all quadruplets summing to target

Problem

Given an integer array nums (length n) and an integer target, return all unique quadruplets [a,b,c,d] such that:

• a + b + c + d == target
• The quadruplet uses four distinct indices from nums
• The output contains no duplicate quadruplets (order of quadruplets and order within a quadruplet do not matter)

Input / Output

• Input: nums: int[] , target: int
• Output: List<List<int>> of unique quadruplets

Constraints (typical interview)

• 0 <= n <= 2000
• Values may be negative and may repeat

Example

• nums = [1,0,-1,0,-2,2] , target = 0
• Output could be: [[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]

Clarifications

• If no quadruplet exists, return an empty list.
• Duplicates in nums are allowed, but duplicates in the returned quadruplets are not.