Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.

4sum.cc

class Solution { //O(n^2) but use set to remove duplicate result
public:
    vector<vector<int> > fourSum(vector<int> &num, int target) {
        // Note: The Solution object is instantiated only once and is reused by each test case.
        sort(num.begin(), num.end());
        map<int, vector<pair<int, int> > > cache;
        for (int i = 0; i < num.size(); ++i) {
            for (int j = i + 1; j < num.size(); ++j) {
                cache[ num[i] + num[j] ].push_back(pair<int, int>(i, j));
            }
        }
        set<vector<int> > ans;
        for (int i = 2; i < num.size(); ++i) {
            for (int j = i + 1; j < num.size(); ++j) {
                int key = target - num[i] - num[j];
                if (cache.count(key)) {
                    for (int k = 0; k < cache[key].size(); ++k) {
                        if (i <= cache[key][k].second) {
                            continue;
                        }
                        vector<int> curr(4);
                        curr[0] = num[ cache[key][k].first ];
                        curr[1] = num[ cache[key][k].second ];
                        curr[2] = num[i];
                        curr[3] = num[j];
                        ans.insert(curr);
                    }
                }
            }
        }
        return vector<vector<int> >(ans.begin(), ans.end());
    }
};