4Sum — DSA · Engineering Playbook

Problem#

Return all unique quadruples in nums that sum to target.

Examples#

nums=[1,0,-1,0,-2,2], target=0 → [[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]].
nums=[2,2,2,2,2], target=8 → [[2,2,2,2]].

Constraints#

1 <= nums.length <= 200.

Approach#

Sort. Two outer loops fix the first two values, then two-pointer the rest. Skip duplicates at every level. Use long long for the sum to avoid overflow.

Solution#

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        sort(nums.begin(), nums.end());
        int n = nums.size();
        vector<vector<int>> ans;
        for (int i = 0; i < n; ++i) {
            if (i > 0 && nums[i] == nums[i-1]) continue;
            for (int j = i + 1; j < n; ++j) {
                if (j > i + 1 && nums[j] == nums[j-1]) continue;
                long long need = (long long)target - nums[i] - nums[j];
                int l = j + 1, r = n - 1;
                while (l < r) {
                    long long s = (long long)nums[l] + nums[r];
                    if (s == need) {
                        ans.push_back({nums[i], nums[j], nums[l], nums[r]});
                        ++l; --r;
                        while (l < r && nums[l] == nums[l-1]) ++l;
                        while (l < r && nums[r] == nums[r+1]) --r;
                    } else if (s < need) ++l;
                    else --r;
                }
            }
        }
        return ans;
    }
};

func fourSum(nums []int, target int) [][]int {
    sort.Ints(nums)
    n := len(nums)
    ans := [][]int{}
    for i := 0; i < n; i++ {
        if i > 0 && nums[i] == nums[i-1] {
            continue
        }
        for j := i + 1; j < n; j++ {
            if j > i+1 && nums[j] == nums[j-1] {
                continue
            }
            need := int64(target) - int64(nums[i]) - int64(nums[j])
            l, r := j+1, n-1
            for l < r {
                s := int64(nums[l]) + int64(nums[r])
                if s == need {
                    ans = append(ans, []int{nums[i], nums[j], nums[l], nums[r]})
                    l++
                    r--
                    for l < r && nums[l] == nums[l-1] {
                        l++
                    }
                    for l < r && nums[r] == nums[r+1] {
                        r--
                    }
                } else if s < need {
                    l++
                } else {
                    r--
                }
            }
        }
    }
    return ans
}

from typing import List

class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        nums.sort()
        n = len(nums)
        ans: List[List[int]] = []
        for i in range(n):
            if i > 0 and nums[i] == nums[i - 1]:
                continue
            for j in range(i + 1, n):
                if j > i + 1 and nums[j] == nums[j - 1]:
                    continue
                need = target - nums[i] - nums[j]
                l, r = j + 1, n - 1
                while l < r:
                    s = nums[l] + nums[r]
                    if s == need:
                        ans.append([nums[i], nums[j], nums[l], nums[r]])
                        l += 1
                        r -= 1
                        while l < r and nums[l] == nums[l - 1]:
                            l += 1
                        while l < r and nums[r] == nums[r + 1]:
                            r -= 1
                    elif s < need:
                        l += 1
                    else:
                        r -= 1
        return ans

var fourSum = function(nums, target) {
    nums.sort((a, b) => a - b);
    const n = nums.length;
    const ans = [];
    for (let i = 0; i < n; i++) {
        if (i > 0 && nums[i] === nums[i - 1]) continue;
        for (let j = i + 1; j < n; j++) {
            if (j > i + 1 && nums[j] === nums[j - 1]) continue;
            const need = target - nums[i] - nums[j];
            let l = j + 1, r = n - 1;
            while (l < r) {
                const s = nums[l] + nums[r];
                if (s === need) {
                    ans.push([nums[i], nums[j], nums[l], nums[r]]);
                    l++;
                    r--;
                    while (l < r && nums[l] === nums[l - 1]) l++;
                    while (l < r && nums[r] === nums[r + 1]) r--;
                } else if (s < need) {
                    l++;
                } else {
                    r--;
                }
            }
        }
    }
    return ans;
};

class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        Arrays.sort(nums);
        int n = nums.length;
        List<List<Integer>> ans = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) continue;
            for (int j = i + 1; j < n; j++) {
                if (j > i + 1 && nums[j] == nums[j - 1]) continue;
                long need = (long) target - nums[i] - nums[j];
                int l = j + 1, r = n - 1;
                while (l < r) {
                    long s = (long) nums[l] + nums[r];
                    if (s == need) {
                        ans.add(Arrays.asList(nums[i], nums[j], nums[l], nums[r]));
                        l++;
                        r--;
                        while (l < r && nums[l] == nums[l - 1]) l++;
                        while (l < r && nums[r] == nums[r + 1]) r--;
                    } else if (s < need) {
                        l++;
                    } else {
                        r--;
                    }
                }
            }
        }
        return ans;
    }
}

function fourSum(nums: number[], target: number): number[][] {
    nums.sort((a, b) => a - b);
    const n = nums.length;
    const ans: number[][] = [];
    for (let i = 0; i < n; i++) {
        if (i > 0 && nums[i] === nums[i - 1]) continue;
        for (let j = i + 1; j < n; j++) {
            if (j > i + 1 && nums[j] === nums[j - 1]) continue;
            const need = target - nums[i] - nums[j];
            let l = j + 1, r = n - 1;
            while (l < r) {
                const s = nums[l] + nums[r];
                if (s === need) {
                    ans.push([nums[i], nums[j], nums[l], nums[r]]);
                    l++;
                    r--;
                    while (l < r && nums[l] === nums[l - 1]) l++;
                    while (l < r && nums[r] === nums[r + 1]) r--;
                } else if (s < need) {
                    l++;
                } else {
                    r--;
                }
            }
        }
    }
    return ans;
}

Editorial#

The classic K-Sum trick: anchor K - 2 indices with nested loops, then two-pointer for the remaining two. Duplicate skipping at all four levels is essential — overlooking one produces duplicate quadruples in the output.

Complexity#

Time: O(n^3).
Space: O(1) ignoring output.

Concept revision#

Two Sum
3Sum