Four Sum

Find all unique quadruplets that sum to a target value.

two-pointers sorting set arrays

Write a function `four_sum(nums, target)` that takes a list of integers `nums` and an integer `target`. The function should return a list of all unique quadruplets `[a, b, c, d]` such that `a + b + c + d == target`. Each quadruplet must be sorted in ascending order. The list of quadruplets must be sorted lexicographically (i.e., by the first element, then the second, etc.) and must not contain duplicate quadruplets.

Constraints

0 <= len(nums) <= 150. Each integer in nums is in the range [-10^6, 10^6]. The target is in the range [-10^6, 10^6]. The solution must run in O(n^3) time or better and use O(n) or O(n^2) extra space.

Example

>>> four_sum([1, 0, -1, 0, -2, 2], 0)
[[-2, -1, 1, 2], [-2, 0, 0, 2], [-1, 0, 0, 1]]
>>> four_sum([], 0)
[]
>>> four_sum([2, 2, 2, 2, 2], 8)
[[2, 2, 2, 2]]
>>> four_sum([1, 2, 3, 4], 10)
[[1, 2, 3, 4]]

30 points ~25 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Sort the array first to make it easy to skip duplicates and use two pointers.

Fix the first two numbers with nested loops, then use two pointers for the remaining two.

When the sum equals the target, add it to results and move both pointers while skipping duplicates.

You can break loops early when the minimum possible sum exceeds the target.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.