3Sum

The problem

Given an integer array, return all unique triples (a, b, c) in the array such that a + b + c = 0. "Unique" means no duplicate triples even if duplicate values exist. It looks like a Diophantine equation — integer solutions of a + b + c = 0 — but the task is different in two ways: the unknowns must come from the given array, not from all integers, and we must enumerate every solution, not just decide whether one exists. That makes it a search problem over the array, and the structure worth exploiting is sortedness, not number theory.

Pattern: sort + two-pointer extension of Two Sum

Two Sum (hashmap) solves the 2-element version in O(n). The natural generalization fixes one element and runs Two Sum on the rest — except a hashmap version of that is hard to deduplicate. So: sort the array, then for each anchor nums[i], run a two-pointer sweep on the suffix for the complement −nums[i]. Sorting makes deduplication trivial: identical adjacent values become a single "skip if same as previous" check. And yes — this is exactly "fix one element, solve Two Sum on what remains": one level of reduction rather than a full recursion. Applying the same move k − 2 times is the standard recursive solution to kSum.

Why pointers at all? Because sorting makes the pair sum monotone in each end: moving the low pointer right can only increase the sum, moving the high pointer left can only decrease it. So each comparison safely throws away every remaining pair that uses the abandoned element — which is how n steps can cover all O(n²) candidate pairs. If the sum is too small, advance the low pointer (the only move that can increase it); too large, retract the high pointer. O(n) per anchor, n anchors: O(n²) total. (A per-anchor hashset also works, but the pointer sweep uses no extra memory and deduplicates naturally on the sorted array.)

Brute force: every triple

def three_sum_brute(nums: list[int]) -> list[list[int]]:
    n = len(nums)
    seen = set()
    out = []
    for i in range(n):
        for j in range(i + 1, n):
            for k in range(j + 1, n):
                if nums[i] + nums[j] + nums[k] == 0:
                    key = tuple(sorted([nums[i], nums[j], nums[k]]))
                    if key not in seen:
                        seen.add(key)
                        out.append(list(key))
    return out

Optimal: sort + two pointers

def three_sum(nums: list[int]) -> list[list[int]]:
    nums.sort()
    out = []
    n = len(nums)
    for i in range(n - 2):
        if nums[i] > 0: break                        # smallest > 0, no triple can sum to 0
        if i > 0 and nums[i] == nums[i - 1]: continue # skip duplicate anchors
        target = -nums[i]
        lo, hi = i + 1, n - 1
        while lo < hi:
            s = nums[lo] + nums[hi]
            if s < target:
                lo += 1
            elif s > target:
                hi -= 1
            else:
                out.append([nums[i], nums[lo], nums[hi]])
                lo += 1; hi -= 1
                while lo < hi and nums[lo] == nums[lo - 1]: lo += 1   # skip dup
                while lo < hi and nums[hi] == nums[hi + 1]: hi -= 1
    return out

Trace

nums = [-1, 0, 1, 2, -1, -4]
sorted: [-4, -1, -1, 0, 1, 2]

i=0, anchor=-4, target=4: two-sum on [-1,-1,0,1,2] for 4. max pair = 1+2 = 3. No hit.
i=1, anchor=-1, target=1: two-sum on [-1,0,1,2].
    lo=-1, hi=2 -> sum 1, hit! append [-1, -1, 2]. lo++, hi--.
    lo=0,  hi=1 -> sum 1, hit! append [-1, 0, 1].  lo++, hi--.  lo>=hi, stop.
i=2, anchor=-1, same as prev — skip.
i=3, anchor=0, target=0: two-sum on [1,2]. min pair = 3 > 0. No hit.

result = [[-1, -1, 2], [-1, 0, 1]]

Complexity

• Time: O(n²). Sort is O(n log n); the nested two-pointer sweep dominates.
• Space: O(1) auxiliary (besides the output and the sort's stack).

Variations worth knowing

• 3Sum Closest: find the triple whose sum is closest to a target. Same skeleton; track best_diff instead of equality. Move pointers toward target.
• 3Sum Smaller: count triples with sum < target. When nums[lo] + nums[hi] < target, every index from lo+1..hi paired with lo also works — add hi − lo in one step.
• 4Sum: two nested anchors + two-pointer. O(n³). Beyond k = 4, recursion with memoization or meet-in-the-middle.
• k-Sum with subquadratic time: the conjectured lower bound for 3Sum is n²; sub-n² in a strong sense is open. Don't be tricked.