Find all unique quadruplets in an array whose sum equals a target.
4Sum
Given an integer array nums and an integer target, return all unique quadruplets [a, b, c, d] such that:
- the four values come from different positions in the array
a + b + c + d == target- the returned quadruplets contain no duplicates
You may return the quadruplets in any order.
This problem is a natural extension of 2Sum and 3Sum: you need to search for combinations of four numbers efficiently while avoiding repeated results.
Input Format
- An integer array
nums - An integer
target
Output Format
- A list of unique quadruplets, where each quadruplet is a list of 4 integers
Constraints
- 4 <= nums.length
- The exact upper bound on
nums.lengthmay vary by platform version - Elements may be negative, zero, or positive
- Return only unique quadruplets
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]]
Explanation
These are the three unique quadruplets whose sum is 0.
Example 2
Input
nums = [2,2,2,2,2], target = 8
Output
[[2,2,2,2]]
Explanation
Only one unique quadruplet exists, even though there are multiple ways to pick the indices.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.