4 Sum

• Time : $O(n^3 + nlogn)$
• Space : $O(1)$

vector<vector<int>> Solution::fourSum(vector<int> &A, int B) {
    vector<vector<int>> res;
    sort(begin(A), end(A));
    int n = A.size();
    for(int i = 0; i < n - 3; i++) {
        if(i and A[i] == A[i-1]) continue;
        if(A[i] + A[i + 1] + A[i + 2] + A[i + 3] > B) break;
        if(A[i] + A[n - 1] + A[n - 2] + A[n - 3] < B) continue;
        for(int j = i + 1; j < n - 2; j++) {
            if(j > i + 1 and A[j] == A[j-1]) continue;
            if(A[i] + A[j] + A[j + 1] + A[j + 2] > B) break;
            if(A[i] + A[j] + A[n - 1] + A[n - 2] < B) continue;
            int l = j + 1, r = n - 1;
            while(l < r) {
                int now = A[i] + A[j] + A[l] + A[r];
                if(now < B) l++;
                else if(now > B) r--;
                else {
                    res.push_back({A[i], A[j], A[l], A[r]});
                    int left = A[l], right = A[r];
                    if(left == right) break;
                    while(l < r and A[l] == left) l++;
                    while(l < r and A[r] == right) r--;
                }
            }
        }   
    }
    return res;
}