Given an integer array nums and an integer target, find all unique quadruplets [nums[a], nums[b], nums[c], nums[d]] — where a, b, c, and d are four different indices — whose values add up to target.
Two quadruplets count as the same if they hold the same four values, so your answer must not contain any quadruplet twice. The order of the quadruplets, and the order of the numbers inside each one, does not matter.
Input: nums = [1,0,-1,0,-2,2], target = 0 Output: [[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]] Three distinct quadruplets sum to 0: (-2)+(-1)+1+2, (-2)+0+0+2, and (-1)+0+0+1. Order does not matter.
Input: nums = [2,2,2,2,2], target = 8 Output: [[2,2,2,2]] Any four of the five 2s sum to 8, but they all form the same value-quadruplet [2,2,2,2], so it appears only once.
- 1 <= nums.length <= 200 - -10^9 <= nums[i] <= 10^9 - -10^9 <= target <= 10^9
4Sum is the k = 4 rung of the kSum ladder, and it exists to cement the pattern from 3Sum: fix an anchor to peel the problem down to a smaller sum problem you already know. Two anchor loops reduce 4Sum to Two Sum. The new wrinkles are one more dedup level and an overflow trap.
10⁹ sum past a 32-bit range, so the running total must be 64-bit.Given nums and a target, return all unique quadruplets of distinct indices whose values sum to target. Order doesn't matter; the same four values count once.
Worked example — nums = [1, 0, -1, 0, -2, 2], target = 0 → sorted [-2,-1,0,0,1,2]
anchors (-2,-1): pair for 3 → (1,2)✓ → [-2,-1,1,2] anchors (-2, 0): pair for 2 → (0,2)✓ → [-2,0,0,2] anchors (-1, 0): pair for 1 → (0,1)✓ → [-1,0,0,1] result: [[-2,-1,1,2], [-2,0,0,2], [-1,0,0,1]] ✓
“Must all four indices be distinct?”
Yes — four different positions, though values may repeat (like the two 0s).
“Is the target arbitrary, or fixed at 0?”
Arbitrary here. The inner pair just needs to sum to target - a - b.
“How are duplicate quadruplets handled?”
Return distinct value-quadruplets only — [2,2,2,2] from five 2s appears once. Dedup at every anchor and pointer level.
“Could the sum overflow?”
Yes — up to four values near 10⁹ gives ~4×10⁹, past 32-bit. Accumulate in 64-bit.
“Return the values or indices?”
The value-quadruplets.
“How large can the array be?”
Up to 200. O(n³) (~8×10⁶) is comfortable; the O(n⁴) brute force is the one to avoid.
A couple of questions.
Four distinct indices, distinct value-quadruplets summing to target?
Values can be large — I'll accumulate sums in 64-bit to avoid overflow.
I'll sort, fix two anchors, and two-pointer the remaining pair — O(n³), skipping duplicates.
Freeze a and b; the remaining pair must sum to target - a - b. So 4Sum is two nested anchor loops wrapped around the same Two Sum core as 3Sum — the kSum reduction, applied twice.
After sorting, the innermost pair is a two-pointer walk (O(n)), giving O(n³) overall and O(1) extra space. Sorting also clusters duplicates, so skip a repeated value at each of the two anchor loops and both pointers — one more level of the same dedup discipline as 3Sum.
This is the trap 3Sum didn't have. With values up to 10⁹, a + b + left + right can exceed a 32-bit integer. Compute the comparison in 64-bit (e.g. long long in C++) so a valid quadruplet isn't missed to wraparound.
| Every quadruplet | Fix two + hash | Sort + two pointers | |
|---|---|---|---|
| Idea | Test all a<b<c<d | Two anchors, then Two Sum by hash | Two anchors, then squeeze inward |
| Time | O(n⁴) | O(n³) | O(n³) |
| Space | O(1) | O(n) | O(1) |
The full code for all three is in the Approaches selector below.
Key takeaway
4Sum = fix two anchors, then Two Sum the rest. Sort once; a two-pointer squeeze handles the inner pair in O(n) for O(n³) total and O(1) space. Skip duplicates at both anchor loops and both pointers to keep quadruplets unique — and accumulate the sum in 64-bit so large values don't overflow. It's the same fix-and-reduce ladder as 2Sum and 3Sum.