// Source : https://oj.leetcode.com/problems/3sum/
// Author : Hao Chen
// Date : 2014-07-22
/**********************************************************************************
*
* 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)
*
*
**********************************************************************************/
#include
#include
#include
#include
#include
using namespace std;
/*
* Simlar like "Two Number" problem, we can have the simlar solution.
*
* Suppose the input array is S[0..n-1], 3SUM can be solved in O(n^2) time on average by
* inserting each number S[i] into a hash table, and then for each index i and j,
* checking whether the hash table contains the integer - (s[i]+s[j])
*
* Alternatively, the algorithm below first sorts the input array and then tests all
* possible pairs in a careful order that avoids the need to binary search for the pairs
* in the sorted list, achieving worst-case O(n^n)
*
* Solution: Quadratic algorithm
* http://en.wikipedia.org/wiki/3SUM
*
*/
vector > threeSum(vector &num) {
vector< vector > result;
//sort the array, this is the key
sort(num.begin(), num.end());
int n = num.size();
for (int i=0; i0 && num[i-1]==num[i]) continue;
int a = num[i];
int low = i+1;
int high = n-1;
while ( low < high ) {
int b = num[low];
int c = num[high];
if (a+b+c == 0) {
//got the soultion
vector v;
v.push_back(a);
v.push_back(b);
v.push_back(c);
result.push_back(v);
// Continue search for all triplet combinations summing to zero.
//skip the duplication
while(low0 && num[high]==num[high-1]) high--;
low++;
high--;
} else if (a+b+c > 0) {
//skip the duplication
while(high>0 && num[high]==num[high-1]) high--;
high--;
} else{
//skip the duplication
while(low> error
vector > combination(vector &v, int k);
bool isSumZero(vector& v);
int sum(vector& v);
vector > threeSum2(vector &num) {
vector< vector > result;
vector< vector > r = combination(num, 3);
for (int i=0; i& v){
return sum(v)==0;
}
int sum(vector& v){
int s=0;
for(int i=0; i > combination(vector &v, int k) {
vector > result;
vector d;
int n = v.size();
for (int i=0; i tmp;
for(int x=0; x 0 ) ? 1 : 0;
ones--;
}
break;
}
if (d[i]==1) ones++;
}
if (!found){
break;
}
}
return result;
}
void printMatrix(vector > &matrix)
{
for(int i=0; i n(a, a+sizeof(a)/sizeof(int));
vector< vector > result = threeSum(n);
printMatrix(result);
return 0;
}