class Solution {
private:
int target, size;
vector<vector<int> > result;
vector<int> tmp, nums;
public:
vector<vector<int> > fourSum(vector<int>& nums, int target) {
int depth = 4;
if (nums.size() >= depth) {
this->target = target;
this->nums = nums;
this->size = this->nums.size();
std::sort(this->nums.begin(), this->nums.end());
depth--;
for (int i = 0; i < this->size - depth; i++) {
if (isTargetExist(i, depth)) {
if (i == 0 || this->nums[i-1] != this->nums[i]) {
findTargets(depth, i, 0);
}
}
}
}
return result;
}
private:
bool isTargetExist(int i, int depth) {
int sum1 = nums[i];
int sum2 = sum1;
for(depth; depth > 0; depth-- ) {
sum1 += nums[size - depth];
sum2 += nums[++i];
}
return sum1 >= target && sum2 <= target;
}
void findTargets(int depth, int index, int sum) {
if (depth == 0) {
sum += nums[index];
if (sum == target) {
tmp.push_back(nums[index]);
result.push_back(tmp);
tmp.pop_back();
}
return;
}
depth--;
sum += nums[index];
tmp.push_back(nums[index]);
for (int i = index + 1; i < this->size - depth; i++) {
if ((i == index + 1) || (nums[i - 1] != nums[i])) {
findTargets(depth, i, sum);
}
}
tmp.pop_back();
}
};