// Source : https://oj.leetcode.com/problems/4sum/
// Author : Hao Chen
// Date : 2014-07-03
/**********************************************************************************
*
* Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d = target?
* Find all unique quadruplets in the array which gives the sum of target.
*
* Note:
*
* Elements in a quadruplet (a,b,c,d) must be in non-descending order. (ie, a ≤ b ≤ c ≤ d)
* The solution set must not contain duplicate quadruplets.
*
* For example, given array S = {1 0 -1 0 -2 2}, and target = 0.
*
* A solution set is:
* (-1, 0, 0, 1)
* (-2, -1, 1, 2)
* (-2, 0, 0, 2)
*
*
**********************************************************************************/
#include
#include
#include
using namespace std;
vector > threeSum(vector num, int target);
/*
* 1) Sort the array,
* 2) traverse the array, and solve the problem by using "3Sum" soultion.
*/
vector > fourSum(vector &num, int target) {
vector< vector > result;
if (num.size()<4) return result;
sort( num.begin(), num.end() );
for(int i=0; i0 && num[i-1]==num[i]) continue;
vector n(num.begin()+i+1, num.end());
vector > ret = threeSum(n, target-num[i]);
for(int j=0; j > threeSum(vector num, int target) {
vector< vector > result;
//sort the array (if the qrray is sorted already, it won't waste any time)
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 == target) {
//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 > target) {
//skip the duplication
while(high>0 && num[high]==num[high-1]) high--;
high--;
} else{
//skip the duplication
while(low > &vv)
{
for(int i=0; i n(a, a+6);
int t = 0;
vector< vector > v = fourSum(n, t);
printMatrix(v);
n.clear();
int b[] = {-1,-5,-5,-3,2,5,0,4};
n.insert(n.begin(), b, b+8);
t = -7;
v = fourSum(n, t);
printMatrix(v);
return 0;
}