4Sum
Last Updated: April 2, 2026
Understanding the Problem
This is a natural extension of the Two Sum and 3Sum problems. Instead of finding pairs or triplets that sum to a target, we need to find all unique groups of four numbers from the array that add up to a given target.
The word "unique" is critical here. If the array contains duplicates, we must not return the same quadruplet twice. For example, given [2, 2, 2, 2, 2] with target 8, the answer is just [[2, 2, 2, 2]], not five copies of it.
So the challenge is twofold: find all valid quadruplets efficiently, and handle duplicates cleanly without relying on a set for deduplication (which adds overhead and is harder to reason about in an interview).
If you have solved 3Sum before, the key insight here is the same. Sort the array first, then use nested loops with two pointers on the inside. The sorting makes duplicate skipping straightforward and enables the two-pointer technique for the innermost pair.
Key Constraints:
1 <= nums.length <= 200— With n at most 200, O(n^3) means 8 million operations, which is perfectly fine. O(n^4) brute force at 1.6 billion is too slow.-10^9 <= nums[i] <= 10^9— Values are large, so the sum of four numbers can overflow a 32-bit integer. We need to uselong(or equivalent) when computing sums.-10^9 <= target <= 10^9— The target can be negative, so our solution must handle negative numbers and negative targets correctly.
Approach 1: Brute Force
Intuition
The most direct approach is to check every possible combination of four distinct indices. For each combination, compute the sum and check if it equals the target. To handle duplicates, we can store results in a set.
This is essentially four nested loops. It works, but it is painfully slow.
Algorithm
- Sort the array (this makes it easier to represent quadruplets in a canonical form for deduplication).
- Use four nested loops to iterate over all combinations of indices
(i, j, k, l)wherei < j < k < l. - For each combination, check if
nums[i] + nums[j] + nums[k] + nums[l] == target. - If so, add the quadruplet to a set (to avoid duplicates).
- Convert the set to a list and return it.
Example Walkthrough
Input:
We check all C(6,4) = 15 combinations of four elements. Three of them sum to 0:
Code
- Time Complexity: O(n^4). Four nested loops, each iterating up to n elements. With n = 200, that is 1.6 billion iterations in the worst case, which is too slow.
- Space Complexity: O(n). The set used for deduplication, plus O(k) for the output where k is the number of unique quadruplets.
The bottleneck is the innermost loop scanning linearly for the fourth number. Since the array is sorted, we can replace the two innermost loops with a two-pointer scan that finds pairs in O(n) instead of O(n^2).
Approach 2: Sorting + Two Pointers
Intuition
If you have solved 3Sum, this approach will feel familiar. The idea is to reduce the problem layer by layer: 4Sum becomes "fix one element, solve 3Sum on the rest." 3Sum becomes "fix one element, solve Two Sum on the rest." Two Sum on a sorted array is a classic two-pointer problem.
So the structure is: sort the array, use two nested loops to fix the first two numbers, then use two pointers (left and right) to find the remaining pair. The sorting serves two purposes: it enables the two-pointer technique, and it makes duplicate skipping trivial.
There is one subtle but important detail: integer overflow. The sum of four numbers, each up to 10^9 in absolute value, can reach 4 * 10^9, which exceeds the 32-bit integer range. We need to use a 64-bit integer type when computing the sum.
The two-pointer technique works because the array is sorted. If the current sum is too small, moving left rightward increases it. If it is too large, moving right leftward decreases it. Combined with duplicate skipping at each loop level, we never produce the same quadruplet twice and never miss a valid one.
Algorithm
- Sort the input array.
- Loop
ifrom0ton - 4. Skip ifnums[i]equals the previous element. - Loop
jfromi + 1ton - 3. Skip ifnums[j]equals the previous element at this level. - Set
left = j + 1andright = n - 1. - While
left < right, compute the sum. If it matches, record the quadruplet and skip duplicates on both sides. If it is too small, moveleftright. If too large, moverightleft.
Example Walkthrough
Code
- Time Complexity: O(n^3). Sorting takes O(n log n). The two nested loops contribute O(n^2), and for each pair, the two-pointer scan is O(n). Total: O(n^2 * n) = O(n^3).
- Space Complexity: O(log n) to O(n). The sorting algorithm's stack space. No additional data structures beyond the output.
The core algorithm is already optimal at O(n^3). But we can add pruning checks to skip impossible iterations early, making it significantly faster in practice.
Approach 3: Sorting + Two Pointers with Pruning
Intuition
The previous approach is already optimal in worst-case complexity. But in practice, we can make it significantly faster by adding early termination checks. If the sum of the four smallest available numbers already exceeds the target, no combination from this point on can work, so we break. If the sum of the current element with the three largest numbers is still below the target, the current element is too small, so we skip it.
These four pruning lines do not change the asymptotic bound, but they eliminate a huge number of unnecessary iterations on most inputs.
Algorithm
- Sort the input array.
- Loop
ifrom0ton - 4. Skip duplicates. Apply min/max sum pruning. - Loop
jfromi + 1ton - 3. Skip duplicates. Apply min/max sum pruning. - Use two pointers
leftandrightto find the remaining pair, same as Approach 2.
Example Walkthrough
Code
- Time Complexity: O(n^3). The worst case is still O(n^3), same as Approach 2. The pruning does not change the asymptotic bound but eliminates many iterations early in practice.
- Space Complexity: O(log n) to O(n). Same as Approach 2. Only the sorting algorithm's stack space is used beyond the output.