Problem #18: 4Sum

Intuition & Strategy Breakdown

Sort the array and use two nested loops to fix two elements. Then use two pointers for the remaining two elements to find quadruplets summing to target, skipping duplicate values.

Python Solution

class Solution:
    def fourSum(self, nums: list[int], target: int) -> list[list[int]]:
        nums.sort()
        res, quad = [], []
        def kSum(k, start, target):
            if k != 2:
                for i in range(start, len(nums) - k + 1):
                    if i > start and nums[i] == nums[i - 1]: continue
                    quad.append(nums[i])
                    kSum(k - 1, i + 1, target - nums[i])
                    quad.pop()
                return
            l, r = start, len(nums) - 1
            while l < r:
                if nums[l] + nums[r] < target: l += 1
                elif nums[l] + nums[r] > target: r -= 1
                else:
                    res.append(quad + [nums[l], nums[r]])
                    l += 1
                    while l < r and nums[l] == nums[l - 1]: l += 1
        kSum(4, 0, target)
        return res

Java Solution

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