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

vector<vector<int> > ans;
vector<int> temp;
bool visit[9999]={false};
bool cmp(vector<int> a,vector<int> b){
    if(a[0]!=b[0])
        {
            return a[0]<b[0];
        }else if(a[1]!=b[1])
        {
            return a[1]<b[1];
        }else if(a[2]!=b[2])
        {
            return a[2]<b[2];
     }
    return true;
}
//C(5,3)=5x4x3/3x2x1=10 所有组合的情况，不考虑内部排序  A(5,3)=5x4x3=60   所有排序的情况，包含内部排序
//要实现C，不需要visit标记，只需要传递上次循环的位置+1作为下一个循环的起始
//要实现A，需要visit标记，每次循环都从0开始
class Solution {
public:
    void DFS(int dep,vector<int> num)
    {
        if(temp.size()==3)
        {   
            vector<int > tt;
            int all_sum=0;
            for(int i=0;i<temp.size();i++)
            {
                all_sum+=temp[i];
                tt.push_back(temp[i]);
            }
            if (all_sum!=0)
                return;
            sort(tt.begin(),tt.end());
            for(int i=0;i<ans.size();i++)
            {
                if(tt[0]==ans[i][0] && tt[1]==ans[i][1])
                    return ;
            }
            ans.push_back(tt);
            return ;
        }

        for(int i=dep;i<num.size();i++)
          {
             temp.push_back(num[i]);
             DFS(i+1,num);
             temp.pop_back();
          }
    }
    vector<vector<int> > threeSum(vector<int> &num) {
        
        DFS(0,num);
        sort(ans.begin(),ans.end(),cmp);
        return ans;
    }
};