# c++ O(n^3) 56ms

• Thanks to 3-Sum question, we can copy the same way to solve 4-Sum problem.

``````class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target) {
vector<vector<int>> result;

if(nums.size()<4)
return result;

std::sort(nums.begin(), nums.end());  //sort the array.

int n = nums.size();

int i,j;
for(i=0; i<n; ++i) {
for(j=n-1; j>0; --j ) {

if((i>0&&nums[i]==nums[i-1]) || (j<n-1&&nums[j]==nums[j+1]))
continue;

int low = i+1;
int high = j-1;

while(low<high) {
if(nums[i]+nums[low]+nums[high]+nums[j] > target)
high--;
else if(nums[i]+nums[low]+nums[high]+nums[j] < target)
low++;
else {
vector<int> tmp;
tmp.push_back(nums[i]);
tmp.push_back(nums[low]);
tmp.push_back(nums[high]);
tmp.push_back(nums[j]);
result.push_back(tmp);

while(low<high && nums[low]==nums[low+1])
low++;
while(low<high && nums[high]==nums[high-1])
high--;

low++;
high--;
}
}
}

}

return result;
}
};
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.