Question:

How to find all the unique quadruples from the given array that sums up to K?

Summary:

This C++ code defines a class Solution with a method fourSum that finds all unique quadruples from a given array whose sum equals a target value s. It utilizes a nested loop approach and binary search to efficiently search for quadruples. The final result is returned as a vector of vectors containing the unique quadruples.

Solution:

// User function template for C++

class Solution{

public:

// arr[] : int input array of integers

// k : the quadruple sum required

vector<vector<int> > fourSum(vector<int> &arr, int s) {

// Your code goes here

if(arr.size()<4){

return {};

}

vector<vector<int>> v;

vector<vector<int>> v1;

set<vector<int>> s1;

sort(arr.begin(),arr.end());

int sum=0;

for(int i=0;i<arr.size()-3;i++){

sum+=arr[i];

for(int j=i+1;j<arr.size()-2;j++){

sum+=arr[j];

for(int k=j+1;k<arr.size()-1;k++){

sum+=arr[k];

int d=s-sum;

int start=k+1,end=arr.size()-1,mid;

while(start<=end){

mid=start+(end-start)/2;

if(arr[mid]==d){

v.push_back({arr[i],arr[j],arr[k],d});

break;

}

else if(arr[mid]>d)

end=mid-1;

else

start=mid+1;

}

sum-=arr[k];

}

sum-=arr[j];

}

sum-=arr[i];

}

if(v.size()==0){

return v;

}

for(vector<int> x: v){

s1.insert(x);

}

for(vector<int> x: s1){

v1.push_back(x);

}

return v1;

}

};

Explanation:

Array Size Check and Initialization:

The code first checks if the size of the input array arr is less than 4. If it is, it returns an empty vector of vectors.
Initializes three vectors: v to store potential quadruples, v1 to store unique quadruples, and s1 as a set to ensure uniqueness.

Sorts the input array arr in non-decreasing order using the sort function from the <algorithm> header.

It uses three nested loops to iterate over all possible combinations of four elements from the input array, starting with the first element and moving forward.

Within the nested loops, it calculates the sum of the current quadruple and then finds the difference d between the target sum s and the current sum.

For each quadruple sum, it performs a binary search to find if there exists a value d in the array that completes the quadruple sum.

If d is found, it adds the quadruple {arr[i], arr[j], arr[k], d} to the vector v.

After completing the search, it checks if v is empty. If it is, it returns an empty vector. It then inserts all elements of v into the set s1 to ensure uniqueness.

Finally, it copies the unique quadruples from the set s1 into the vector v1 and returns v1 as the result.

>Activating Virtual environment in visual studio code windows 11

>Fix webapp stops working issue in Django- Python webapp

>Creating a form in Django to upload a picture from website

>Sending Audio file from Django to Vue

>How to keep all query parameters intact when changing page in Django?

>Solved: TaskList View in Django