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 + 3 < n; i++) {
            for(int j = i + 1; j + 2 < n; j++) {
                long long required = (long long)target - (nums[i] + nums[j]);

                int L = j + 1, R = n - 1;

                while(L < R) {
                    long long sum = (long long)nums[L] + nums[R];

                    if(sum > required) R -= 1;
                    else if(sum < required) L += 1;
                    else {
                        vector<int> quadruple = {nums[i], nums[j], nums[L], nums[R]};
                        res.push_back(quadruple);

                        while((L < R) and (nums[L] == nums[L + 1])) L += 1;
                        while((R > L) and (nums[R] == nums[R - 1])) R -= 1;

                        L += 1;
                        R -= 1;
                    }
                }

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

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

        return res;
    }
};