题目来源:http://www.leetcode.com/onlinejudge
解题报告:
简单的用递归实现的,有一点是注意数组中可能会有重复数字,所以要考虑结果中不要输出重复结果。
#include <iostream> #include <algorithm> #include <vector> using namespace std; class Solution { public: void f(int index, vector<int> temp, vector<int> &num, vector<vector<int> > &result, int sum) { if (temp.size() == 3) { if (sum==0) result.push_back(temp); return; } if (index == num.size()) return; if (sum + num[index] > 0) return; int i = index; int next = i+1; while(next < num.size() && num[next] == num[i]) next++; temp.push_back(num[index]); f(i+1, temp, num, result, sum+num[index]); temp.pop_back(); f(next, temp, num, result, sum); } vector<vector<int> > threeSum(vector<int> &num) { // Start typing your C/C++ solution below // DO NOT write int main() function sort(num.begin(),num.end()); vector<vector<int> > result; vector<int> temp; f(0,temp,num,result,0); return result; } };
附录:
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 solution set is: (-1, 0, 1) (-1, -1, 2)