Understanding the Problem
The "4 Sum" problem asks us to find all unique quadruplets (groups of four numbers) in a given array that add up to a specific target sum. The array can include positive numbers, negative numbers, and duplicates. For example, if the input is nums = [1, 0, -1, 0, -2, 2]
and target = 0
, we need to find all unique sets of four numbers whose sum equals 0.
Example
Let’s take nums = [1, 0, -1, 0, -2, 2]
and target = 0
.
After sorting the array, we get: [-2, -1, 0, 0, 1, 2]
We want to find combinations like [-2, -1, 1, 2]
because -2 + -1 + 1 + 2 = 0
.
Step-by-Step Approach
Instead of using brute force to try every combination of 4 numbers (which is very slow), we use a structured and efficient method:
Step 1: Sort the Array
Sorting helps us to:
- Quickly skip duplicate values
- Use the two-pointer technique for finding pairs
Step 2: Use Nested Loops to Fix First Two Numbers
We use two nested for
loops to pick the first and second numbers of the quadruplet.
Step 3: Two-Pointer Technique for Remaining Two Numbers
Once the first two numbers are fixed, we use two pointers — left
and right
— to scan for the remaining two numbers that complete the quadruplet.
Step 4: Skip Duplicates
After each valid combination, we move the left
and right
pointers to skip over any duplicate values to avoid repeating the same quadruplets in the result.
Incorporating Edge Cases
Case 1: Empty Array or Less Than 4 Elements
If the array is empty or has fewer than 4 elements, we can’t form a quadruplet. Return an empty list: []
Case 2: All Elements Are the Same
Example: [2, 2, 2, 2, 2]
with target = 8 → Only one valid quadruplet: [2, 2, 2, 2]
. Skip remaining duplicates.
Case 3: No Valid Combination
If no group of 4 numbers adds up to the target, return an empty list.
Case 4: Negative and Positive Mix
The presence of both negative and positive numbers means valid quadruplets can be scattered across the array — sorting helps align them for scanning.
Why This Solution Works
By sorting and using nested loops with two pointers:
- We reduce time complexity to
O(n³)
— much faster than checking every O(n⁴)
combination.
- We ensure that no duplicate sets are added to the result.
- We handle all edge cases with clear, logical checks.
Finally
This method is efficient, beginner-friendly, and scalable. It teaches good habits like sorting early, avoiding duplicate work, and breaking problems down step-by-step.
Comments
Loading comments...