4Sum.txt

class Solution {
public:
    vector<vector<int> > fourSum(vector<int> &num, int target) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        vector<vector<int> > rets;
        if (num.size() < 4)
            return rets;
        sort(num.begin(), num.end());
        for (size_t i = 0; i < num.size() - 3; i++) {
            if ((i > 0) && (num[i] == num[i-1]))
                continue;
            for (size_t j = i + 1; j < num.size() - 2; j++) {
                if ((j > i + 1) && (num[j] == num[j-1]))
                    continue;
                size_t l = j + 1, u = num.size() - 1;
                while (l < u) {
                    long long sum = (long long)num[i] + num[j] + num[l] + num[u];
                    if (sum == target) {
                        rets.push_back(vector<int> (4, num[i]));
                        rets.back()[1] = num[j];
                        rets.back()[2] = num[l];
                        rets.back()[3] = num[u];
                    }
                    if (sum < target)
                        while ((++l < u) && (num[l] == num[l-1]));
                    else
                        while ((--u > l) && (num[u] == num[u+1]));
                }
            }
        }
        return rets;
    }
};