1 vector<vector<int> > res; 2  3 void dfs(vector<int> &num, vector<int> ans, int pos, int left, int sum) { 4   if (left == 0) { 5     if (sum == 0) 6       res.push_back(ans); 7     return; 8   } 9 10   if (left == 1) {11     int l = pos;12     int r = num.size() - 1;13     while (l <= r) {14       int m = (l + r) / 2;15       if (num[m] + sum == 0) {16         ans.push_back(num[m]);17         res.push_back(ans);18         ans.pop_back();19         return;20       }21       else if (num[m] + sum < 0)22         l = m + 1;23       else24         r = m - 1;25     }26     return;27   }28 29   unordered_set<int> old;30   for (int i = pos; i < num.size(); i++) {31     if (old.find(num[i]) != old.end())32       continue;33     if (sum + left * num[i] > 0)34       break;35     if (sum + num[i] + (left - 1 ) * num[num.size() - 1] < 0)36       continue;37     old.insert(num[i]);38     ans.push_back(num[i]);39     dfs(num, ans, i + 1, left - 1, sum + num[i]);40     ans.pop_back();41   }42 }43 44 vector<vector<int> > threeSum(vector<int> &num) {45   sort(num.begin(), num.end());46   dfs(num, vector<int>(), 0, 3, 0);47   return res;48 }