4Sum

Four choices suggest an O(n^4) search. Sorting changes the last two choices into a controlled walk.

The answer direction

Given an integer array nums and a target, return every unique quadruplet of values whose four elements come from distinct indices and sum to target.

The 4Sum solution is:

1. Sort the array.
2. Fix the first value with i.
3. Fix the second value with j > i.
4. Search the remaining suffix with two pointers, k = j + 1 and l = n - 1.
5. Skip duplicate values at each decision layer.

The indices must be distinct, but the output is unique by values. If the input contains enough separate copies, [0, 0, 0, 0] is valid once—not once for every possible choice of four indices.

Sorting gives us two assets at once: equal values become adjacent, and the remaining pair has monotone movement. That reduces the worst-case search from O(n^4) to O(n^3).

Recognize the fixed-element reduction

The pattern is easier to rebuild than to memorize. Look for four signals:

• You must enumerate a fixed number of values.
• The values satisfy a sum relation.
• Sorting can establish useful order.
• After fixing enough values, two values remain in a suffix.

Once i and j are fixed, the problem becomes:

Find two values in the sorted suffix whose sum is target - nums[i] - nums[j].

That is the two-pointer remainder. This is a fixed-element reduction: two nested choices expose a two-element problem that sorted order can solve in one scan.

This is not a sliding window. The pointers are not maintaining a valid contiguous range. They move in opposite directions because sorted order proves which candidate states are impossible. The array becomes a one-way ratchet: every movement removes states we no longer need to inspect.

Start with the brute-force baseline

The direct approach chooses four increasing indices:

for i in range(n):
    for j in range(i + 1, n):
        for k in range(j + 1, n):
            for l in range(k + 1, n):
                if nums[i] + nums[j] + nums[k] + nums[l] == target:
                    # record the quadruplet
                    pass

Increasing indices enforce distinctness. But the four loops inspect every possible index quadruplet, giving O(n^4) time.

After fixing i and j, the last two loops are wasteful. In a sorted suffix, k is the smallest available left endpoint and l is the largest available right endpoint. Their sum tells us which side can still repair the total:

• If the total is too small, move k right to increase it.
• If the total is too large, move l left to decrease it.
• If the total matches, record the values and move both pointers.

For one fixed pair (i, j), each pointer crosses its suffix at most once. The outer two loops create O(n^2) fixed pairs, so the full search is O(n^3) after sorting.

Make each state variable earn its place

For a sorted array, the indices have a strict order:

i < j < k < l

Each variable has a specific obligation:

• i chooses the first value.
• j chooses the second value after i.
• k starts immediately after j.
• l starts at the end of the array.
• k < l guarantees that the last two indices differ.

At every pointer state, calculate:

total = nums[i] + nums[j] + nums[k] + nums[l]

If total < target, keeping k cannot help. nums[k] is already the smallest available left value, so pairing it with an earlier right endpoint would make the total no larger. Advance k.

If total > target, keeping l cannot help. nums[l] is already the largest available right value, so pairing it with a later left endpoint would make the total no smaller. Decrement l.

The sorted array acts like a one-way ratchet: each move removes a region that cannot contain a new answer.

Prune impossible bounds safely

Pruning is optional for correctness, but it makes the algorithm stop looking at dead regions early. The rule is simple: compare the smallest and largest possible completion with the target, then distinguish whether later choices can recover.

For a fixed i, the smallest possible quadruplet is:

nums[i], nums[i + 1], nums[i + 2], nums[i + 3]

If that sum is greater than target, break the entire i loop. Every later i is at least as large, so later quadruplets cannot become smaller.

The largest possible quadruplet for this i is:

nums[i], nums[n - 3], nums[n - 2], nums[n - 1]

If that sum is less than target, continue to the next i. This fixed choice cannot work, but a larger i might increase the total enough.

For fixed i and j, apply the same reasoning:

• If nums[i] + nums[j] + nums[j + 1] + nums[j + 2] > target, break the j loop. Later j values are no smaller.
• If nums[i] + nums[j] + nums[n - 2] + nums[n - 1] < target, continue to the next j. A later j may still work.

This distinction is worth saying aloud in an interview:

If the smallest completion is already too large, later choices cannot recover, so break. If the largest completion is still too small, only this fixed choice failed, so continue.

These checks preserve the O(n^3) worst-case bound. They simply cut away work when the sorted bounds make failure obvious.

Duplicate skipping is part of correctness

Duplicate handling is not cleanup after the search. It is part of defining which value quadruplet owns each result.

At the first two decision layers, skip a value if the same value was already used at that layer:

if i > 0 and nums[i] == nums[i - 1]:
    continue

if j > i + 1 and nums[j] == nums[j - 1]:
    continue

The boundary on j matters. The first j after i is allowed to equal nums[i]; a valid result may need two equal values from two distinct positions. We skip only repeated j values for the same i.

After a match, move both pointers and skip equal suffix values:

k += 1
l -= 1

while k < l and nums[k] == nums[k - 1]:
    k += 1

while k < l and nums[l] == nums[l + 1]:
    l -= 1

Record first. Move second. Skip third.

For fixed i and j, a later k with the same value produces the same first three output values. To reach the same target, it would need the same fourth value, so it would reproduce the quadruplet already emitted. The same argument applies to repeated l values.

Consider:

nums   = [0, 0, 0, 0, 0]
target = 0

There are multiple valid index selections, but only one unique value quadruplet:

[0, 0, 0, 0]

Distinct indices and unique output values are separate obligations. The index order enforces the first; duplicate skipping enforces the second.

The pointer invariant and correctness

For fixed i and j, maintain this invariant:

Every pair outside the current interval [k, l] has either been proved impossible for the remaining target or has been represented by an emitted quadruplet whose duplicate-equivalent states were skipped.

Suppose the current total is too small. Because the array is sorted, nums[k] is the smallest available left value. Every pair using this same k and a right endpoint l' <= l has a sum no greater than the current pair. Those pairs are also too small, so advancing k removes only impossible states.

Suppose the total is too large. nums[l] is the largest available right value. Every pair using this same l and a left endpoint k' >= k has a sum no smaller than the current pair. Those pairs are also too large, so decrementing l removes only impossible states.

When the total matches, the four values form a valid quadruplet. Moving both pointers consumes that pair, and skipping equal values removes only alternate index representations of the same value sequence.

The coverage argument needs one precise distinction: the loops enumerate index positions, not abstract values. After sorting, the first occurrence of a value at a given layer acts as that prefix's representative index. Later equal positions at the same layer would create the same value prefix, so they are skipped. The suffix still begins strictly after the chosen indices, so it preserves any multiplicity required by a valid quadruplet—for example, choosing two 0 values at different positions.

Therefore, every feasible value quadruplet has a representative path through the loops, and each emitted value quadruplet has only one owner at each duplicate layer. The algorithm neither loses a unique value sequence nor emits the same one twice.

Dry run: movement and duplicate control

Use this sorted input:

nums   = [-2, -1, 0, 0, 1, 2]
target = 0

Selected states look like this:

i	j	k	l	Total	Action
0	1	2	5	-1	Too small; advance k
0	1	3	5	-1	Too small; advance k
0	1	4	5	0	Emit [-2, -1, 1, 2]; move both
0	2	3	5	0	Emit [-2, 0, 0, 2]; move both
0	3	—	—	—	Skip duplicate j because nums[3] == nums[2]
1	2	2	5	1	Too large; decrement l
1	2	2	4	0	Emit [-1, 0, 0, 1]; move both

For i = 0 and j = 1, the first two states are too small. Advancing k is safe because no smaller right endpoint can repair either sum. After the match at k = 4, l = 5, both pointers move to k = 5, l = 4, and that suffix scan ends.

The next fixed pair is i = 0, j = 2. It finds [0, 2] in the remaining suffix and emits [-2, 0, 0, 2]. After that match, k and l cross. The next outer-loop position is j = 3, but nums[3] == nums[2], so the duplicate guard skips it: the prefix [-2, 0] already owns that value choice. Then i = 1 begins a new prefix layer, which is why j = 2 is valid again.

When i = 1 and j = 2, the initial total with the largest right endpoint is 1, already too large. Decreasing l exposes 1 and produces [-1, 0, 0, 1].

Implement the 4Sum solution in Python

from typing import List


def four_sum(nums: List[int], target: int) -> List[List[int]]:
    n = len(nums)
    result: List[List[int]] = []

    if n < 4:
        return result

    # Use sorted(nums) instead when the caller's list must remain unchanged.
    nums.sort()

    for i in range(n - 3):
        if i > 0 and nums[i] == nums[i - 1]:
            continue

        # Smallest possible quadruplet for this i is already too large.
        if nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target:
            break

        # Largest possible quadruplet for this i is still too small.
        if nums[i] + nums[n - 3] + nums[n - 2] + nums[n - 1] < target:
            continue

        for j in range(i + 1, n - 2):
            if j > i + 1 and nums[j] == nums[j - 1]:
                continue

            # Smallest completion for this i and j is too large.
            if nums[i] + nums[j] + nums[j + 1] + nums[j + 2] > target:
                break

            # Largest completion for this i and j is still too small.
            if nums[i] + nums[j] + nums[n - 2] + nums[n - 1] < target:
                continue

            k = j + 1
            l = n - 1

            while k < l:
                total = nums[i] + nums[j] + nums[k] + nums[l]

                if total < target:
                    k += 1
                elif total > target:
                    l -= 1
                else:
                    result.append([nums[i], nums[j], nums[k], nums[l]])

                    k += 1
                    l -= 1

                    while k < l and nums[k] == nums[k - 1]:
                        k += 1

                    while k < l and nums[l] == nums[l + 1]:
                        l -= 1

    return result

Use this three-part verification bridge before trusting the function:

1. Index order: the loop starts and k = j + 1 enforce i < j < k, while k < l keeps the final indices distinct.
2. Monotonicity: sorting justifies every pointer move and every break or continue bound check; no movement is a guess.
3. Duplicate ownership: the guards at i, j, k, and l let one representative index path emit each value quadruplet.

Python integers do not have the fixed-width overflow behavior found in languages such as Java or C++. In a fixed-width implementation, use a sufficiently wide type for the intermediate total, because four valid input values can produce a sum outside the type used for one input value.

I prefer this canonical traversal to generating every candidate and deduplicating the result afterward. A set can remove repeated outputs, but it hides why duplicates occur and makes the index argument harder to inspect. Here, the traversal itself explains uniqueness.

Complexity and edge cases

Sorting costs O(n log n). The two outer loops contribute O(n^2), and each fixed pair gets a linear two-pointer scan. The total is:

Time: O(n log n + n^3) = O(n^3)

Pruning may reduce practical work without changing the worst-case bound.

If sorting is in place, auxiliary algorithm space is O(1) beyond the returned results, although the sorting implementation may use internal memory. The output itself can contain many quadruplets and must be counted separately.

Check these cases deliberately:

• Fewer than four values: return an empty list.
• Exactly four values: return one quadruplet only when its sum matches.
• No match: finish without appending a result.
• Mixed signs or a negative target: no positivity assumption is needed.
• Repeated values: test all-zero input and repeated values mixed with distinct values.
• Many valid quadruplets: ensure deduplication does not remove genuinely different value sequences.
• Large-magnitude values: check intermediate-sum behavior in the language being used.
• Input mutation: use sorted(nums) instead of nums.sort() when the caller's list must remain unchanged.

Common failure modes are diagnostic:

Failure	Consequence
Skip sorting	Pointer direction and adjacent duplicate checks lose their justification
Start k at j	An index can be reused
Skip j, k, or l duplicates	The same value quadruplet appears repeatedly
Move only one pointer after a match	The scan can rescan equivalent states
Skip before recording a match	A valid representation can disappear
Use continue where a bound requires break	Later fixed choices may be handled incorrectly
Use a narrow type for the total	Intermediate addition can overflow

The transferable rule is compact:

When a sorted array asks for all unique fixed-size combinations, fix enough values to leave a two-element remainder, then use a pointer invariant to eliminate impossible states.

Before relying on the template, verify three things: indices remain strictly increasing, every pointer move follows from sorted monotonicity, and duplicate skipping removes repeated representations rather than valid value combinations. That is how we rebuild 4Sum when the surface details change instead of reciting a memorized loop.