4Sum
Find every unique quadruplet that sums to a target: sort, fix two numbers with nested loops, and sweep the rest with two pointers, skipping duplicates.
Problem Understanding
4Sum: given an array nums and a target, return every unique quadruplet [a, b, c, d] of distinct indexes whose values sum to target.
Example: nums = [1, 0, -1, 0, -2, 2], target = 0 returns [[-2,-1,1,2], [-2,0,0,2], [-1,0,0,1]].
The Intuition: 3Sum With One More Loop
3Sum fixes one number and finds the other two with two pointers. 4Sum fixes two numbers and does the same:
- Sort, so the sum tells you which way to move.
- Fix
i, thenj > i. - Sweep
landrover the rest: too small moveslright, too big movesrleft, equal is recorded. - Skip duplicates at each level: a repeated
ivalue, a repeatedjvalue, and copies oflafter a match.
The same idea generalises to kSum: recurse down to a two-pointer base case. For the closest sum instead of an exact one, see 3Sum Closest.
Interactive Walkthrough
The sorted array carries four pointers: the fixed pair i and j (tinted) and the sweep l and r (filled). A match turns all four green. Try All repeats to see the duplicate skips at work.
Dry Run Table
Input: sorted nums = [-2, -1, 0, 0, 1, 2], target = 0
| i | j | Quadruplet found |
|---|---|---|
| -2 | -1 | [-2, -1, 1, 2] |
| -2 | 0 | [-2, 0, 0, 2] |
| -2 | 0 (repeat) | skipped |
| -1 | 0 | [-1, 0, 0, 1] |
| -1 | 0 (repeat) | skipped |
Answer: 3 quadruplets.
The Solution Template
Two nested loops plus a two-pointer sweep. Java, C++ and C add in 64 bits; C grows its result array as needed.
4Sum Code
1var fourSum = function(nums, target) {2 nums.sort((a, b) => a - b);3 const n = nums.length, res = [];4 for (let i = 0; i < n - 3; i++) {5 if (i > 0 && nums[i] === nums[i - 1]) continue;6 for (let j = i + 1; j < n - 2; j++) {7 if (j > i + 1 && nums[j] === nums[j - 1]) continue;8 let l = j + 1, r = n - 1;9 while (l < r) {10 const s = nums[i] + nums[j] + nums[l] + nums[r];11 if (s === target) {12 res.push([nums[i], nums[j], nums[l], nums[r]]);13 l++;14 while (l < r && nums[l] === nums[l - 1]) l++;15 } else if (s < target) l++;16 else r--;17 }18 }19 }20 return res;21};
Edge Cases & Common Mistakes
- Fewer than four numbers: the loops never run; return an empty list.
- Overflow: four values near 10⁹ exceed 32 bits; sum them as 64-bit integers.
- Skipping
jduplicates withj > 0: must bej > i + 1, or a valid second number equal to the first is wrongly skipped. - Forgetting to skip copies of
lafter a match: the same quadruplet is reported repeatedly. - Using a set of tuples instead: works, but skipping duplicates during the sweep is cleaner and avoids extra memory.
Summary
Sort the array, fix two numbers with nested loops, and sweep the remainder with two pointers: too small moves left up, too big moves right down, and equal is recorded. Skip repeated values at every level. O(n³) time and O(1) extra space.
More practice: DSA interview questions with answers · patterns cheat sheet