#include <vector>
#include <algorithm>
#include <iostream>

using std::cout;
using std::vector;
using std::sort;
class Solution {
public:
 vector<vector<int>> fourSum(vector<int>& nums, int target) {
 vector<vector<int>> vv;
 sort(nums.begin(),nums.end());
 int a,b,c,d,left,right;
 long sum;
 for(size_t i = 0;i < nums.size();++ i)
 {
 // 减枝
 if(nums[i] > target && target > 0) break;
 a = nums[i];
 // 过滤a
 if(i > 0 && nums[i] == nums[i - 1]) continue;
 for(size_t j = i + 1;j < nums.size();++ j)
 {
 if(a + nums[j] > target && target > 0) break;
 // 过滤b
 if(j > i + 1 && nums[j] == nums[j - 1]) continue;
 b = nums[j];
 left = j + 1;
 right = nums.size() - 1;
 while(left < right)
 {
 c = nums[left];
 d = nums[right];
 sum = (long)a + b + c + d;
 if(sum < target) ++ left;
 else if(sum > target) -- right;
 else
 {
 vv.push_back({a,b,c,d});
 // 去重
 while(left < right && nums[left] == nums[left + 1]) ++ left;
 while(left < right && nums[right] == nums[right - 1]) --right;

 ++ left;
 -- right;
 }
 }
 
 }

 }
 return vv;
 }
};


int main(int argc, char const *argv[])
{
 Solution s;
 vector<int> v({2,2,2,2,2});
 vector<vector<int>> vv = s.fourSum(v,8);
 for(auto &v : vv)
 {
 for(auto & num : v)
 {
 cout << num << " ";
 }
 cout << "\n";
 }
 getchar();
 return 0;
}