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. http://www.leetcode.com/onlinejudge

leetcode_4sum.cpp

#include <algorithm>
#include <vector>
#include <string>
#include <tr1/unordered_map>
using namespace std;

class Solution {
public:
    vector<vector<int> > fourSum(vector<int> &num, int target) {
        vector< vector<int> > ret;
        tr1::unordered_map< int, vector<int> > flag;
        tr1::unordered_map< int, vector<int> >::iterator it;
        tr1::unordered_map< string, bool > used;
        char buf[64];
        for (int i = 0; i < num.size(); ++i) {
            for (int j = i + 1; j < num.size(); ++j) {
                int sum = num[i] + num[j];
                it = flag.find(target - sum);
                if (it != flag.end()) {
                    vector<int>& tmp = it->second;
                    for (int k = 0; k < tmp.size(); ++k) {
                        vector<int> t(4);
                        t[0] = num[i];
                        t[1] = num[j];
                        t[2] = tmp[k];
                        t[3] = target - t[0] - t[1] - t[2];
                        sort(t.begin(), t.end());
                        sprintf(buf, "%d %d %d %d", t[0], t[1], t[2], t[3]);
                        if (used.find(buf) == used.end()) {
                            used[buf] = true;
                            ret.push_back(t);
                        }
                    }
                }
            }
            for (int j = 0; j < i; ++j) {
                int sum = num[i] + num[j];
                it = flag.find(sum);
                if (it == flag.end()) {
                    vector<int> t(1);
                    t[0] = min(num[i], num[j]);
                    flag[sum] = t;
                }
                else {
                    it->second.push_back(min(num[i], num[j]));
                }
            }
        }
        return ret;
    }
};