4Sum Problem and Solution

1. Introduction

A comprehensive guide to solving the "4Sum" problem in multiple programming languages (C++, Java, and Python), including detailed explanations and outputs.

The "4Sum" problem is an extension of the classic "3Sum" problem. It involves finding all unique quadruplets in the given array that sum up to a given target value.

2. Problem

Given an array nums of n integers and an integer target, are there elements a, b, c, and d in nums such that a + b + c + d = target? Find all unique quadruplets in the array that give the sum of the target.

3. Solution in C++

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

vector<vector<int>> fourSum(vector<int>& nums, int target) {
    vector<vector<int>> res;
    if (nums.empty()) return res;
    int n = nums.size();
    sort(nums.begin(), nums.end());

    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            int target_2 = target - nums[i] - nums[j];
            int front = j + 1;
            int back = n - 1;
            while (front < back) {
                int two_sum = nums[front] + nums[back];
                if (two_sum < target_2) front++;
                else if (two_sum > target_2) back--;
                else {
                    vector<int> quadruplet(4, 0);
                    quadruplet[0] = nums[i];
                    quadruplet[1] = nums[j];
                    quadruplet[2] = nums[front];
                    quadruplet[3] = nums[back];
                    res.push_back(quadruplet);

                    // Processing duplicates of Number 3
                    while (front < back && nums[front] == quadruplet[2]) ++front;

                    // Processing duplicates of Number 4
                    while (front < back && nums[back] == quadruplet[3]) --back;
                }
            }

            // Processing duplicates of Number 2
            while (j + 1 < n && nums[j + 1] == nums[j]) ++j;
        }

        // Processing duplicates of Number 1
        while (i + 1 < n && nums[i + 1] == nums[i]) ++i;
    }
    return res;
}

// Example usage
int main() {
    vector<int> nums = {1, 0, -1, 0, -2, 2};
    int target = 0;
    auto quadruplets = fourSum(nums, target);
    for (auto &quad : quadruplets) {
        for (int num : quad) {
            cout << num << " ";
        }
        cout << endl;
    }
    return 0;
}

Output:

-2 -1 1 2
-2 0 0 2
-1 0 0 1

Explanation:

1. fourSum in C++ sorts the array and then uses two loops to fix the first two numbers.

2. For the remaining two numbers, it uses a two-pointer approach.

3. The function avoids duplicates and finds all unique quadruplets that sum up to the target.

4. Solution in Java

import java.util.*;

public class FourSum {
    public static List<List<Integer>> fourSum(int[] nums, int target) {
        Arrays.sort(nums);
        List<List<Integer>> res = new ArrayList<>();
        for (int i = 0; i < nums.length - 3; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) continue; // skip duplicates
            for (int j = i + 1; j < nums.length - 2; j++) {
                if (j > i + 1 && nums[j] == nums[j - 1]) continue; // skip duplicates
                int left = j + 1, right = nums.length - 1;
                while (left < right) {
                    int sum = nums[i] + nums[j] + nums[left] + nums[right];
                    if (sum == target) {
                        res.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right]));
                        while (left < right && nums[left] == nums[left + 1]) left++; // skip duplicates
                        while (left < right && nums[right] == nums[right - 1]) right--; // skip duplicates
                        left++; right--;
                    } else if (sum < target) {
                        left++;
                    } else {
                        right--;
                    }
                }
            }
        }
        return res;
    }

    // Example usage
    public static void main(String[] args) {
        int[] nums = {1, 0, -1, 0, -2, 2};
        int target = 0;
        List<List<Integer>> quadruplets = fourSum(nums, target);
        System.out.println(quadruplets);
    }
}

Output:

[[-2, -1, 1, 2], [-2, 0, 0, 2], [-1, 0, 0, 1]]

Explanation:

1. Java's fourSum method also sorts the array and uses a nested loop for the first two numbers.

2. It employs a two-pointer technique for finding the remaining two numbers.

3. The method ensures to skip over duplicates and collects all unique quadruplets.

5. Solution in Python

def four_sum(nums, target):
    nums.sort()
    res, quad = [], []
    def k_sum(start, k, 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])
                k_sum(i + 1, k - 1, target - nums[i])
                quad.pop()
            return
        l, r = start, len(nums) - 1
        while l < r:
            s = nums[l] + nums[r]
            if s == target:
                res.append(quad + [nums[l], nums[r]])
                l += 1
                while l < r and nums[l] == nums[l - 1]:
                    l += 1
            elif s < target:
                l += 1
            else:
                r -= 1

    k_sum(0, 4, target)
    return res

# Example usage
nums = [1, 0, -1, 0, -2, 2]
target = 0
print("Quadruplets:", four_sum(nums, target))

Output:

Quadruplets: [[-2, -1, 1, 2], [-2, 0, 0, 2], [-1, 0, 0, 1]]

Explanation:

1. Python's four_sum uses a recursive approach to handle the k-sum problem, generalizing to 4-sum.

2. It sorts the array and then recursively reduces the problem to 2-sum.

3. Avoids duplicates and collects all unique quadruplets that sum up to the target.