The 4 Sum problem asks us to find sets of four numbers in an array that add up to a given target. A brute force method would try every possible combination of four numbers, but this becomes inefficient very quickly as the array grows. Instead, we use a more optimal and structured approach.
Understanding the Problem
We are given an array that may contain positive, negative, or duplicate numbers. We need to find all unique sets of four numbers (quadruplets) such that their sum equals the given target. The key challenge is not just finding these combinations, but doing so efficiently while avoiding duplicates in the result.
How the Efficient Approach Works
First, we sort the array. Sorting helps in two ways:
- It lets us skip duplicate numbers easily
- It enables the use of the two-pointer technique
We fix the first two numbers using two nested loops. For each pair, we use two pointers — left
and right
— to find the remaining two numbers that make the total sum equal to the target.
Handling Duplicates
Since the array can contain duplicates, we must make sure that we don’t return the same set more than once. To handle this:
- We skip duplicate elements while selecting the first and second numbers in the outer loops.
- We also skip duplicates while moving the left and right pointers after finding a valid quadruplet.
What Happens in Special Cases?
- Empty array: No elements means no quadruplets can be formed → return
[]
.
- Fewer than 4 elements: Again, not enough numbers → return
[]
.
- All elements are the same: If four or more elements match the target when summed, return one quadruplet only.
- No valid combination exists: If no group of 4 numbers can meet the target, return an empty list.
Why This Works
The sorted array and two-pointer technique ensure that we don’t waste time checking every possible combination. This reduces the time complexity to O(n3)
, which is significantly better than the naive O(n4)
approach.
By combining sorting, nested loops, and careful duplicate skipping, we ensure the solution is both efficient and accurate.