Back to Problems

4Sum

Hard
Two Pointers

Given an array nums of n integers, return an array of all the unique quadruplets [nums[a], nums[b], nums[c], nums[d]] such that:

• 0 <= a, b, c, d < n • a, b, c, and d are distinct • nums[a] + nums[b] + nums[c] + nums[d] == target

You may return the answer in any order.

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]]

Example 2

Input: nums = [2,2,2,2,2], target = 8
Output: [[2,2,2,2]]

Constraints

  • •1 <= nums.length <= 200
  • •-10^9 <= nums[i] <= 10^9
  • •-10^9 <= target <= 10^9
Show Hints (3)
Hint 1: This is an extension of 3Sum. Fix two elements, then use two pointers for the remaining two.
Hint 2: Sort the array first and skip duplicates at each level to avoid duplicate quadruplets.
Hint 3: Use early termination: if the smallest possible sum exceeds target, or the largest possible sum is less than target, skip.
Loading editor...

Test Results

Click "Run" to execute your code against test cases

AI Tutor

Socratic guidance - I'll ask questions, not give answers

AI Tutor
Hello! I'm your AI tutor, here to guide you through this problem using the Socratic method. I won't give you direct answers, but I'll ask questions and provide hints to help you discover the solution yourself. What's your first instinct when you look at this problem? What approach comes to mind?