/**
knakul853
**/
class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {

        int n = (int)nums.size();

        if(nums.size() < 0) return {{}};

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

        vector<vector<int>>ans;

        for( int i=0;i<n;i++)
        {
           int target3 = target - nums[i];


            for(int j=i+1; j<n; j++ )
            {
               int target2 = target3 - nums[j];


                int front = j +1;
                int back = n-1;

                while(front < back)
                {
                    if( nums[front] + nums[back] < target2)front++;

                    else if(nums[front] + nums[back] > target2) back--;

                    else{

                        vector<int>temp={nums[i], nums[j], nums[front], nums[back]};
                        ans.push_back(temp);
                        while( front < back && nums[front] == temp[2]) front++;
                        while( front < back && nums[back] == temp[3]) back--;
                    }

                }

                while(j+1 < n && nums[j] == nums[j+1])j++;
            }

            while(i+1 < n && nums[i] == nums[i+1])i++;
        }

        return ans;
    }
};