# Straightforward 104ms C++ solution based on 2sum and 3sum approach

• This is similar to the approach for 2sum and 3sum. The 2sum portion is solved via a linear time search. This search is done inside a quadratic time scan of the other two numbers in the sum, producing a n^3 algorithm overall. We can optimize by skipping over equal numbers in the array (done with the do loops).

``````class Solution {
public:
vector<vector<int> > fourSum(vector<int> &num, int target) {
if (num.size() < 4) { return {}; }
vector<vector<int> > result;
sort(num.begin(), num.end());
int i = 0;
while (i < num.size() - 3) {
int j = i + 1;
while (j < num.size() - 2) {
int two_sum_target = target - num[i] - num[j];
int k1 = j + 1, k2 = num.size() - 1;
while (k1 < k2) {
int value = num[k1] + num[k2];
if (value == two_sum_target) {
result.emplace_back(vector<int>{num[i], num[j], num[k1], num[k2]});
do { k1++; } while (k1 < k2 && num[k1] == num[k1 - 1]);
do { k2--; } while (k1 < k2 && num[k2] == num[k2 + 1]);
} else if (value < two_sum_target) {
do { k1++; } while (k1 < k2 && num[k1] == num[k1 - 1]);
} else {
do { k2--; } while (k1 < k2 && num[k2] == num[k2 + 1]);
}
}
do { j++; } while (j < num.size() - 2 && num[j] == num[j - 1]);
}
do { i++; } while (i < num.size() - 3 && num[i] == num[i - 1]);
}
return result;
}
};``````

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