https://leetcode.com/problems/4sum/
#include<algorithm>
#include<vector>
using namespace std;
class Solution {
public:
void _sum(vector<int>& nums,int l,vector<vector<int>> &ans,int target,vector<int> &x,int n) {
int L=nums.size();
if(n>L-l || n*nums[l] > target || n*nums.back()<target) return;
if(n==2){
int r=nums.size()-1;
while(l<r){
if(nums[l]+nums[r]>target) --r;
else if(nums[l]+nums[r]<target) ++l;
else{
x.push_back(nums[l]);
x.push_back(nums[r]);
ans.push_back(x);
x.pop_back();
x.pop_back();
++l;
--r;
while(l<r && nums[l]==nums[l-1]) ++l;
while(l<r && nums[r]==nums[r+1]) --r;
}
}
}
else{
for(int i=l;i<=L-n;++i){
if(i!=l && nums[i]==nums[i-1]) continue;
x.push_back(nums[i]);
vector<vector<int>> tmp;
_sum(nums,i+1,tmp,target-nums[i],x,n-1);
for(auto &xx:tmp)
ans.push_back(xx);
x.pop_back();
}
}
return;
}
vector<vector<int>> fourSum(vector<int>& nums, int target) {
/*
和第15题共用以上函数
*/
sort(nums.begin(),nums.end());
vector<vector<int>> ans;
vector<int> x;
_sum(nums,0,ans,target,x,4);
return ans;
}
};