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]]
This is a bit tricky problem first we need to sort the array as now we have to find all combination of 4 numbers that makes the sum equal to the target so in this, we approach the problem with 2 for loops where first loop i.e i 0 to n-1 (where n is the size of the array) and j from i to n then we add the 2 numbers and subtract that from the target we the required number which we want to get than inside the j loop we do a binary search and make 2 pointers to j+1 and n and use the same approach we did in 3 sums but now we will also check for repeated numbers for optimal and non-repeating answers so we while loop to counter this problem of repeating answers.
class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target) {
vector<vector<int>> res;
sort(nums.begin(),nums.end());
int n=nums.size()-1;
for(int i=0;i<n-1;)
{
for(int j=i+1;j<n;)
{
int sum=nums[i]+nums[j];
int req=target-sum;
int lo=j+1,hi=n;
while(lo<hi)
{
int sum2=nums[lo]+nums[hi];
if(sum2==req)
{
res.push_back({nums[i],nums[j],nums[lo++],nums[hi--]});
while(lo<n and nums[lo]==nums[lo-1]) lo++;
while(hi>j and nums[hi]==nums[hi+1]) hi--;
}
else if(sum2>req) hi--;
else lo++;
}
do{j++;}while(j<n and nums[j]==nums[j-1]);
}
do{i++;}while(i<n and nums[i]==nums[i-1]);
}
return res;
}
};