Problem Statement

Given an array nums of n integers, return an array of all the 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

You may return the answer in any order.

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

Problem Link

4Sum - LeetCode

Code

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        
        int n = nums.size();
        sort(nums.begin(),nums.end());
        vector<vector<int>> res;
        for(int i=0;i<n;)
        {
            for(int j=i+1;j<n-1;)
            {
                int l = j+1;
                int h = n-1;
                long long twoSum = (long long)target - nums[i] - nums[j];
                while(l<h)
                {
                    if(nums[l]+nums[h]==twoSum)
                    {
                        
                        res.push_back({nums[i],nums[j],nums[l],nums[h]});
                        
                        
                        while(h-1>=0&&nums[h]==nums[h-1])
                            h--;
                        h--;
                    }
                    
                    else if(nums[l]+nums[h]>twoSum)
                    {
                        while(h-1>=0&&nums[h]==nums[h-1])
                            h--;
                        h--;
                    }
                    else
                    {
                        while(l+1<n&&nums[l]==nums[l+1])
                            l++;
                        l++;
                    }
                }
                
              while(j+1<n&&nums[j]==nums[j+1])
                            j++;
                        j++;
            }
            while(i+1<n&&nums[i]==nums[i+1])
                            i++;
                        i++;
        }
        
        return res;
        
    }
};