18. 4Sum - Solutions and Explanation

Problem Statement

The task is to find all unique groups of four different integers from the given array nums that add up to a specified number, target. Each group, or quadruplet, must consist of elements that are distinct from each other in terms of their indices in the array. This means a quadruplet [nums[a], nums[b], nums[c], nums[d]] should satisfy the conditions that none of the indices a, b, c, d are the same and the values at these indices sum up to target. Importantly, the solution should consist of all such unique quadruplets, without any repetitions, and can be returned in any order.

Examples

Example 1

Input:

nums = [1,0,-1,0,-2,2], target = 0

Output:

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

Example 2

Input:

nums = [2,2,2,2,2], target = 8

Output:

[[2,2,2,2]]

Constraints

1 <= nums.length <= 200
-109 <= nums[i] <= 109
-109 <= target <= 109

Approach and Intuition

The problem essentially involves exploring combinations of four numbers in an array to find specific sums. To approach this:

Start by sorting the array. Sorting helps in skipping duplicates and also in the efficient checking of pair sums.
Use a four-level nested loop to explore possible groups of four:
- For the first element a, iterate from the start to near the end.
- For the second element b, iterate from a+1 to further.
- Before moving deeper into the loops for c and d, check if the sum of potential minimum or maximum values exceeds or doesn’t meet target. This helps in pruning unnecessary iterations.
- For the third element c, iterate from b+1 onwards and for the fourth d, from c+1 to the end.
Sum the values at these indices (nums[a], nums[b], nums[c], nums[d]). If it matches the target, add the quadruplet to the results.
To ensure that only unique quadruplets are included, continue the loop using the next distinct element whenever a valid combination is found or the target isn't met. For example, after finding a valid nums[a], skip all following elements that are the same as nums[a] to avoid duplicate quadruplets.
Since the problem can have multiple quadruplets, leveraging hash-based structures might help in storing and verifying the uniqueness of these quadruplets efficiently.

Example walkthrough from given data:

For nums = [1,0,-1,0,-2,2] and target = 0. First, sort the array to [-2, -1, 0, 0, 1, 2]. Begin with -2 as a, and proceed to choose distinct -1, 0, and 2 by checking and adjusting the sum at each step to finally match the target.
In the case of nums = [2, 2, 2, 2, 2] and target = 8, after sorting, iterate to find the quadruplet [2, 2, 2, 2] which sums to the target. Given the repetitive elements, it needs special attention to avoid generating duplicates beyond the unique possibilities.

Solutions

C++
Java
JavaScript
Python

                            cpp
                            
                        
class Solution {
public:
    vector<vector<int>> findQuadruplets(vector<int>& nums, int target) {
        sort(nums.begin(), nums.end());
        return findKSum(nums, target, 0, 4);
    }

    vector<vector<int>> findKSum(vector<int>& nums, long long targetSum, int start,
                             int k) {
        vector<vector<int>> result;

        if (start == nums.size()) {
            return result;
        }

        long long average_value = targetSum / k;

        if (nums[start] > average_value || average_value > nums.back()) {
            return result;
        }

        if (k == 2) {
            return pairSum(nums, targetSum, start);
        }

        for (int i = start; i < nums.size(); ++i) {
            if (i == start || nums[i - 1] != nums[i]) {
                for (vector<int>& subset :
                     findKSum(nums, targetSum - nums[i], i + 1, k - 1)) {
                    result.push_back({nums[i]});
                    result.back().insert(result.back().end(), subset.begin(),
                                      subset.end());
                }
            }
        }

        return result;
    }

    vector<vector<int>> pairSum(vector<int>& nums, long long targetSum, int start) {
        vector<vector<int>> result;
        unordered_set<long long> seen;

        for (int i = start; i < nums.size(); ++i) {
            if (result.empty() || result.back()[1] != nums[i]) {
                if (seen.count(targetSum - nums[i])) {
                    result.push_back({int(targetSum - nums[i]), nums[i]});
                }
            }
            seen.insert(nums[i]);
        }

        return result;
    }
};

This solution is ideally designed to find all unique quadruples in an array that sum up to a target value. The main functionality is handled by the findQuadruplets function which heavily utilizes the helper function findKSum to facilitate the process of finding ( k )-sum combinations. Here’s a breakdown of how the implementation tackles the problem:

Initially, the input array of numbers is sorted. This is crucial for efficiently finding tuples and avoiding duplicates.
findKSum is a recursive function that simplifies the problem from finding quadruples to finding triples, pairs, and ultimately singles that sum up to given targets by decrementing ( k ).
If ( k ) reduces to 2, the routine switches to a more specific function pairSum, optimized for finding two numbers that sum up to the desired target.
To avoid duplicates and to optimize lookup times for pair sums, an unordered set seen is utilized in pairSum. As we progress through the array, we check if the complement of the current number (target minus current number) exists in seen.
The main function leverages findKSum to find all possible combinations recursively by iteratively considering each element and attempting to find ( k-1 ) sum results that, combined with the current element, equal the target sum.

This method ensures that the response includes only unique sets of numbers due to two primary checks:

Skipping the same element in the top level of recursion to prevent reconsidering the same starting number.
Ensuring in pairSum that we don’t add a pair which was just added to the result.

These details, combined with sorting and the set operations, help maintain an efficient and comprehensive solution to the problem of finding quads in an array that sum to a specific target value.

                            java
                            
                        
class Solution {
    public List<List<Integer>> findFourSum(int[] numbers, int targetSum) {
        Arrays.sort(numbers);
        return findKSum(numbers, targetSum, 0, 4);
    }

    public List<List<Integer>> findKSum(int[] numbers, long target, int start, int k) {
        List<List<Integer>> result = new ArrayList<>();

        // Return empty result if start exceeds the number array
        if (start == numbers.length) {
            return result;
        }

        // Calculate the required average value of k numbers
        long averageValue = target / k;

        // Check if the current subset cannot fulfill the requirement
        if (numbers[start] > averageValue || averageValue > numbers[numbers.length - 1]) {
            return result;
        }

        // Base case: when we break down to two sum problems
        if (k == 2) {
            return twoNumberSum(numbers, target, start);
        }

        // Recursive call into kSum reducing the problem size
        for (int i = start; i < numbers.length; ++i) {
            if (i == start || numbers[i - 1] != numbers[i]) {
                for (List<Integer> subset : findKSum(
                    numbers, 
                    target - numbers[i],
                    i + 1,
                    k - 1
                )) {
                    result.add(new ArrayList<>(Arrays.asList(numbers[i])));
                    result.get(result.size() - 1).addAll(subset);
                }
            }
        }

        return result;
    }

    public List<List<Integer>> twoNumberSum(int[] numbers, long target, int start) {
        List<List<Integer>> result = new ArrayList<>();
        Set<Long> seen = new HashSet<>();

        for (int i = start; i < numbers.length; ++i) {
            if (result.isEmpty() || result.get(result.size() - 1).get(1) != numbers[i]) {
                if (seen.contains(target - numbers[i])) {
                    result.add(Arrays.asList((int)(target - numbers[i]), numbers[i]));
                }
            }
            seen.add((long) numbers[i]);
        }

        return result;
    }
}

In the provided Java solution for the 4Sum problem, the objective is to find all unique sets of four numbers in an array that sum up to a given target value. The main approach taken here is to use a recursive function that handles the k-sum problem, which can be broken down into simpler two-sum problems as the base case.

Here's an explanation of how the solution works:

Firstly, the input array is sorted. This is a preparatory step that helps in applying the two-sum approach effectively.
The findFourSum function serves as a public interface. It initializes the process by calling the recursive findKSum function with k set to 4.
The findKSum function attempts to solve the problem by using recursion to reduce the k-sum problem to simpler and smaller problems:
- Checking for the base case where if k == 2, a two-number sum function (twoNumberSum) is employed.
- Beyond the base case, the function iteratively tries to find the (k-1)-sum for the remaining target (target - numbers[i]), where i is the current index.
The twoNumberSum handles the two-sum problem specifically:
- It uses a HashSet to track the already seen numbers which efficiently helps in checking if the complement (target - current number) exists in the seen set.
- Once a valid pair is found, it's added to the result list.

Through recursion and efficient use of hash sets for the two-sum part, this solution manages to handle and unravel the complexities associated with multi-number sum problems. The choice of data structures and the method of breaking down the problem are critical for managing what would otherwise be a computationally intensive process. This approach ensures that we efficiently find all unique quadruples that sum up to the target value without redundant calculations.

                            js
                            
                        
const quadSum = function (numbers, targetSum) {
    function pairSum(index, target) {
        let results = [];
        let seenNumbers = new Set();
        for (let j = index; j < numbers.length; j++) {
            if (results.length == 0 || results[results.length - 1][1] != numbers[j]) {
                if (seenNumbers.has(target - numbers[j])) {
                    results.push([target - numbers[j], numbers[j]]);
                }
            }
            seenNumbers.add(numbers[j]);
        }
        return results;
    }
    function multiSum(index, target, k) {
        let results = [];
        if (index === numbers.length) {
            return results;
        }
        let averageValue = Math.floor(target / k);
        if (
            numbers[index] > averageValue ||
            averageValue > numbers[numbers.length - 1]
        ) {
            return results;
        }
        if (k === 2) {
            return pairSum(index, target);
        }
        for (let i = index; i < numbers.length; i++) {
            if (i === index || numbers[i - 1] !== numbers[i]) {
                multiSum(i + 1, target - numbers[i], k - 1).forEach((set) => {
                    results.push([numbers[i]].concat(set));
                });
            }
        }
        return results;
    }
    numbers.sort((a, b) => a - b);
    return multiSum(0, targetSum, 4);
};

The provided JavaScript function quadSum is designed to solve the problem of finding all unique quadruplets in a sorted array that sum up to a given target value. Here's a concise summary of how this function works:

The primary function quadSum uses a sorting step to process the input array followed by a recursive function multiSum for finding quadruplets.
Within the quadSum function, the array numbers is first sorted to facilitate ordered processing.
The multiSum function is a recursive helper that aims to find k-sum combinations:
- It checks base cases for recursion termination and handles conditions to skip unnecessary processing.
- For k = 2, it defers to another helper function pairSum to find pairs of numbers that sum up to the target. This uses a Set for efficient lookup of complement values.
- For k > 2, it recursively calls itself to find smaller combinations (i.e., (k-1)-sums) and then combines these with the current number to form k-sums.
The pairSum helper function loops through the segment of the array from a starting index and uses a Set to keep track of numbers seen so far, which simplifies the process of checking for pairs that meet the target sum by looking for complements.

To implement this solution, consider how the sorting of the array aids in avoiding duplicates and how using Sets and recursive decomposition simplifies finding multilevel combinations. The quadSum function effectively breaks down the problem into manageable subproblems, making it a powerful approach to tackle the 4-sum problem using a combination of sorting, hashing, and recursive partitioning strategies.

                            python
                            
                        
class Solution:
    def findFourElements(self, nums: List[int], target: int) -> List[List[int]]:

        def kSum(num_list: List[int], target_val: int, k: int) -> List[List[int]]:
            result = []

            if not num_list:
                return result

            avg = target_val // k

            if avg < num_list[0] or num_list[-1] < avg:
                return result

            if k == 2:
                return twoElementSum(num_list, target_val)

            for i in range(len(num_list)):
                if i == 0 or num_list[i - 1] != num_list[i]:
                    for elemSubset in kSum(num_list[i + 1:], target_val - num_list[i], k - 1):
                        result.append([num_list[i]] + elemSubset)

            return result

        def twoElementSum(elements: List[int], target_sum: int) -> List[List[int]]:
            outcome = []
            seen_elements = set()

            for index in range(len(elements)):
                if not outcome or outcome[-1][1] != elements[index]:
                    if target_sum - elements[index] in seen_elements:
                        outcome.append([target_sum - elements[index], elements[index]])
                seen_elements.add(elements[index])

            return outcome

        nums.sort()
        return kSum(nums, target, 4)

The provided Python 3 code aims to solve the "4Sum" problem, where the task is to find all unique quadruplets in a list that sum up to a given target. The solution employs a recursive approach to break down the problem into smaller ones, mainly using a generalized "kSum" method to handle different cases, particularly the 2-sum and k-sum scenarios.

The kSum function recursively reduces the problem by decreasing the value of k until it becomes 2, where a simpler two-sum problem is solved using the twoElementSum function.
twoElementSum utilizes a set to rapidly check for the existence of the complement values (target_sum - current element), which are needed to form pairs that meet the target sum criteria.
The main method findFourElements begins by sorting the input array, which is a prerequisite for the algorithms used in the helpers to work properly since they rely on the sorted nature of the array to eliminate duplicates and achieve the correct pairings.

The overarching strategy is efficient for finding not just 4-element sums but can be adapted for other k-values, as kSum divides the problem into smaller sums recursively until it can be solved directly via the two-element sum approach.

Comments

No comments yet.

4Sum

Problem Statement

Examples

Example 1

Example 2

Constraints

Approach and Intuition

Solutions

Comments

Products

Features

Solutions

Marketplace

Resources

Company

Tech Talks

Vultr Blogs