4Sum

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:

1. Start by sorting the array. Sorting helps in skipping duplicates and also in the efficient checking of pair sums.

2. 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.

3. 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.

4. 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.

5. 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

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;
    }
};