4Sum
The key idea
Sort first, then fix the two outer numbers with nested loops and let two pointers collapse the remaining pair. Sorting makes duplicates adjacent, so you can skip a repeated value at every level with one comparison — that is what keeps the quadruplets distinct without a hash set.
Problem
Given an array nums of n integers, return all the unique quadruplets [nums[a], nums[b], nums[c], nums[d]] such that:
- a, b, c, and d are distinct indices, and
- nums[a] + nums[b] + nums[c] + nums[d] == target.
You may return the answer in any order. The solution set must not contain duplicate quadruplets. Note that the four values can be large, so a sum of four of them may overflow a 32-bit integer.
Constraints
1 <= nums.length <= 200-10^9 <= nums[i] <= 10^9-10^9 <= target <= 10^9
Examples
Input: nums = [1,0,-1,0,-2,2], target = 0
Output: [[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
Input: nums = [2,2,2,2,2], target = 8
Output: [[2,2,2,2]]
Complexity
Time: O(n^3) Space: O(1)
See the full solution
- ✓Full worked approach
- ✓Reference code in 5 languages
- ✓Problem-solving tips
- ✓Step-by-step animated visualization