10. 4Sum

Medium · Array

Find all unique quadruplets in an array that sum to a target value. You are given an array `nums` and an integer `target`. Return every unique set of four numbers from `nums` that add up to `target`. Each quadruplet should be returned as a sorted array [a, b, c, d] where a ≤ b ≤ c ≤ d. The outer list of quadruplets must be sorted lexicographically (as if using JSON.stringify and string comparison). Input format: [nums, target] where nums is an array of integers and target is an integer. Return an array of arrays, where each inner array is a sorted quadruplet.

Examples

Example 1
Input: [[1,0,-1,0,-2,2], 0]
Output: [[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
Explanation: Three distinct quadruplets, canonical order
Example 2
Input: [[2,2,2,2,2], 8]
Output: [[2,2,2,2]]
Explanation: Only one quadruplet possible

Constraints