4Sum extends Two Sum and 3Sum: instead of pairs or triplets, we need all unique groups of four numbers that add up to a given target.

The uniqueness requirement drives most of the implementation work. If the array contains duplicates, we must not return the same quadruplet twice. Given [2, 2, 2, 2, 2] with target 8, the answer is [[2, 2, 2, 2]], not five copies of it.

The challenge is twofold: find all valid quadruplets efficiently, and produce each one exactly once. A hash set can deduplicate results after the fact, but sorting the array up front lets us skip duplicates during enumeration and enables a two-pointer scan for the innermost pair.

Key Constraints:

Intuition

Check every combination of four distinct indices, compute each sum, and compare it against the target. Matches go into a set so that duplicate quadruplets collapse to one entry.

Four nested loops implement this directly, at the cost of examining every combination whether or not it has any chance of matching.

Algorithm

Visualization and Code

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).

Intuition

The problem reduces layer by layer. 4Sum is "fix one element, solve 3Sum on the rest." 3Sum is "fix one element, solve Two Sum on the rest." Two Sum on a sorted array is a two-pointer scan.

So the structure is: sort the array, fix the first two numbers with nested loops, then move two pointers (left and right) toward each other to find the remaining pair. Sorting serves two purposes: it enables the two-pointer scan, and it places equal values next to each other so duplicates can be skipped with a single comparison.

One implementation detail: 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. Compute the sum in a 64-bit type.

Algorithm

Visualization and Code

O(n^3) is the best this strategy can do asymptotically, but bound checks at each loop level can skip large parts of the search space in practice.

Intuition

Two checks at each loop level cut the work. At the i level: if nums[i] plus the three elements right after it already exceeds the target, every later choice of i has an even larger minimum because the array is sorted, so we can break out of the loop entirely instead of continuing. If nums[i] plus the three largest elements still falls short of the target, this i is too small but a later one might not be, so we continue to the next iteration. The same pair of checks runs inside the j loop with nums[i] held fixed.

These four pruning lines leave the asymptotic bound unchanged but skip entire branches of the search on most inputs.

Algorithm

Visualization and Code

Every version so far hardcodes four levels of iteration. The same reduction works for any k, and writing it recursively produces one solution that covers 2Sum, 3Sum, 4Sum, and beyond.

Intuition

Approach 2 reduced 4Sum to 3Sum and 3Sum to Two Sum by hand, one nested loop per layer. The reduction is identical at every layer, so it can be written once as a recursive function: kSum(start, target, k) fixes one element and delegates the rest to kSum(start + 1, target - element, k - 1). When k reaches 2, the sorted two-pointer scan takes over as the base case.

Deduplication carries over unchanged. Each recursion level skips elements equal to their predecessor, and the base case skips repeated pair values, so every unique quadruplet is produced once.

The payoff is generality: the same function solves 5Sum or 6Sum by changing the initial k. Passing the running target down as a 64-bit value also handles overflow in one place, since each subtraction can push the remaining target outside the 32-bit range.

Algorithm

Visualization and Code