4-Sum Problem

Problem Overview

The problem in focus is famously known as 4Sum. The objective of this problem is to find all unique quadruplets in an array that add up to a given target. This problem builds upon the concepts familiar in simpler problems like 2Sum and 3Sum.

• Given: An integer array nums and an integer target.
• Output: All unique quadruplets [nums[a], nums[b], nums[c], nums[d]] such that:
  • 0 <= a, b, c, d < n
  • a, b, c, and d are distinct
  • nums[a] + nums[b] + nums[c] + nums[d] == target
  • The subsets are distinct, i.e., the quadruplets should not repeat.

Understanding the Problem

The 4Sum problem requires finding sets of four numbers that sum up to a given target. It asks us to list all combinations without repeating sets. Here, it's key to also manage duplicates within the given array to ensure subsets are indeed unique.

For example, given nums = [1, 0, -1, 0, -2, 2] and target = 0, a valid output would be:

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

Key DSA Concepts and Theory

Arrays

An array is a simple data structure used for storing similar types of data. It is particularly useful in problems dealing with combinations and permutations.

Two-Pointers Technique

This technique involves using two pointers to traverse through an array and is widely used in problems involving sorted arrays or lists.

Sorting

Sorting helps unify the order of elements, which simplifies the processing of combinations, especially when paired with the two-pointers technique.

Solution Approach

The main approach to solving 4Sum is an extension of the two-pointers method used in 3Sum problems. It involves iterating through the list and systematically using two pointers to find quadruplets that sum to the target. Here is the step-by-step breakdown:

1. Sort the Array: Begin by sorting the array to simplify handling duplicates and enable the two-pointer searching mechanism effectively.
2. Outer Two Loops: Fix the first two numbers of the quadruplet using two nested loops.
3. Two-Pointer Scan: For the remaining two numbers, use the two-pointer approach to find pairs that sum to the target deducted by the sum of the first two numbers.
4. Avoid Duplicates: Ensure you skip any duplicate numbers to prevent repeated quadruplets.
5. Collect Results: Store valid quadruplets and continue scanning the array.

Below are the code implementations in both C++ and Java:

C++ Code

#include <vector>
#include <algorithm>

std::vector<std::vector<int>> fourSum(std::vector<int>& nums, int target) {
    std::vector<std::vector<int>> result;
    std::sort(nums.begin(), nums.end());

    for (int i = 0; i < nums.size(); i++) {
        if (i > 0 && nums[i] == nums[i - 1]) continue;
        for (int j = i + 1; j < nums.size(); j++) {
            if (j > i + 1 && nums[j] == nums[j - 1]) continue;
            int left = j + 1, right = nums.size() - 1;
            while (left < right) {
                long sum = static_cast<long>(nums[i]) + nums[j] + nums[left] + nums[right];
                if (sum == target) {
                    result.push_back({nums[i], nums[j], nums[left], nums[right]});
                    while (left < right && nums[left] == nums[left + 1]) left++;
                    while (left < right && nums[right] == nums[right - 1]) right--;
                    left++;
                    right--;
                } else if (sum < target) {
                    left++;
                } else {
                    right--;
                }
            }
        }
    }
    return result;
}

Java Code

import java.util.*;

class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> result = new ArrayList<>();
        Arrays.sort(nums);

        for (int i = 0; i < nums.length; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) continue;
            for (int j = i + 1; j < nums.length; j++) {
                if (j > i + 1 && nums[j] == nums[j - 1]) continue;
                int left = j + 1, right = nums.length - 1;
                while (left < right) {
                    long sum = (long) nums[i] + nums[j] + nums[left] + nums[right];
                    if (sum == target) {
                        result.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right]));
                        while (left < right && nums[left] == nums[left + 1]) left++;
                        while (left < right && nums[right] == nums[right - 1]) right--;
                        left++;
                        right--;
                    } else if (sum < target) {
                        left++;
                    } else {
                        right--;
                    }
                }
            }
        }
        return result;
    }
}

Time and Space Complexity Analysis

• Time Complexity: (O(n^3))

  • Sorting the array takes (O(n \log n)) time.
  • The three nested loops partially integrate with the two-pointer scan, leading to an overall complexity of (O(n^3)).

• Space Complexity: (O(1))

  • Apart from the space needed for output storage, the approach does not utilize any additional space significantly.

Common Mistakes to Avoid

1. Handling Duplicates Incorrectly: Failure to skip duplicate numbers can cause repeated quadruplets in the result list.
2. Integer Overflow: Ensure you handle large sums appropriately, potentially using a larger data type like long to avoid overflow issues.

Similar Problems on LeetCode

1. 3Sum (LeetCode #15)
2. 2Sum (LeetCode #1)
3. 3Sum Closest (LeetCode #16)
4. 4Sum II (LeetCode #454)

Additional Resources and References

• LeetCode Problem Discuss Forums
• Two-Pointer Technique Explained

This article has delved into the solution for the 4Sum problem, detailing its approach and covering essential data structures and algorithms concepts. Understanding this problem helps solidify one's problem-solving skills in dealing with sum-related array challenges.