给定一个数组，里面的是任意整数，可能有重复，再给定一个目标T，从数组中找出所有和为T的K个数，要求结果中没有重复。
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)
思路很容易就想到，还是利用将问题规模最小化的原则，简化问题成两个数的和为M的问题。整体的思想就是动态规划的思想了，只是特别需要注意的是要找出所有的可能。另外还需要特别处理重复和每个可能的内部顺序。4-sum的代码如下：
vector<vector<int>> fourSum(vector<int>& nums, int target) {
std::sort(nums.begin(), nums.end());
vector<vector<int>> ans;
if (nums.size() >= 4)
{
findSum(ans, nums, target, 4, 0);
std::set<vector<int> > dset;
vector<vector<int> >::iterator itr = ans.begin();
while (itr != ans.end())
{
std::reverse(itr->begin(), itr->end());
dset.insert(*itr);
++itr;
}
ans.clear();
std::set<vector<int> >::iterator itr2 = dset.begin();
while (itr2 != dset.end())
{
ans.push_back(*itr2++);
}
}
return ans;
}
void findSum(vector<vector<int> > &ans, vector<int>& nums, int target, int count, int start) {
int sz = nums.size();
if (!(count < 2 || start > sz - 1))
{
int p = nums[start];
if (count > 2)
{
findSum(ans, nums, target - p, count - 1, start + 1);
vector<vector<int> >::iterator itr = ans.end();
while (itr !=ans.begin())
{
--itr;
if (itr->size() == count - 1)
{
itr->push_back(p);
}
else
break;
}
findSum(ans, nums, target, count, start + 1);
}
else if (count == 2)
{
int i = start;
int j = sz - 1;
while (i < j)
{
if (target == nums[i] + nums[j])
{
vector<int> v;
v.reserve(4);
v.push_back(nums[j]);
v.push_back(nums[i]);
ans.push_back(v);
i++;
}
else if ( nums[i] + nums[j] > target)
j--;
else
i++;
}
}
}
}