题解 | #数组中相加和为0的三元组#

思路一：固定一个数，选择其他两个数，复杂度O(n^3)。 思路二：dfs回溯法，注意在dfs中不能sort(path)以避免回溯顺序打乱，注意多个元素共同排序的lambda。

class Solution {
public:
    void dfs(const vector<int>& num,vector<vector<int>>& result,vector<int>& path,int index){
        if(path.size()>3) return;
        if(path.size()==3){
            if(path[0]+path[1]+path[2]==0){
                //sort(path.begin(),path.end());
                result.push_back(path);
            }
            return;
        }
        for(int i=index;i<num.size();i++){
            path.push_back(num[i]);
            dfs(num,result,path,i+1);
            path.pop_back();
        }
    }
    
    vector<vector<int> > threeSum(vector<int> &num) {
        vector<vector<int>> result{};
        vector<int> path{};
        dfs(num,result,path,0);
        for(auto& vec:result) sort(vec.begin(),vec.end());
        
        auto cmp = [](vector<int> a , vector<int> b) {
		    if (a[ 0 ] == b[ 0 ]) {
			    if (a[ 1 ] == b[ 1 ]) {
				    if (a[ 2 ] == b[ 2 ]) {
					    return false;
				    }
				    else return a[ 2 ] < b[ 2 ];
			    }
			    else return a[ 1 ] < b[ 1 ];
		    }
		    else return a[ 0 ] < b[ 0 ];
	    };
        
        sort(result.begin(),result.end(),cmp);
        auto end_iter=unique(result.begin(),result.end());
        vector<vector<int>> three{result.begin(),end_iter};
        return three;
    }
};