Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero. Note: Elements in a triplet (a,b,c) must be in non-descending order. (ie, a ? b ? c) The solution set must not contain duplicate triplets. For example, given array S = {-1 0 1 2 -1 -4}, A sol…

3Sum.cpp

class Solution {
public:
    vector<vector<int> > res;
    vector<int> cur;
    vector<vector<int> > threeSum(vector<int> &num) {
        res.clear();
        cur.clear();
        sort(num.begin(), num.end());
        solve(num, 0, 0, 0);
        return res;
    }
    
    void solve(vector<int>& num, int depth, int cal, int index) {
        if(depth == 3) {
            if(cal == 0) {
                res.push_back(cur);
            }
            return;
        }
        int* pre = NULL;
        for(int i = index; i < num.size(); ++i) {
            if(pre == NULL) {
                pre = new int(num[i]);
            } else if(*pre == num[i]) {
                continue;
            }
            
            *pre = num[i];
            cur.push_back(num[i]);
            solve(num, depth + 1, cal + num[i], i + 1);
            cur.pop_back();
            
        }
        
        if(pre) {
            delete pre;
        }
    }
};