# ReaL simple c++ solution with in-line comments

• ``````class Solution {
public:

vector<vector<int>> fourSum(vector<int>& nums, int target) {
vector<vector<int>> ans;
int len=nums.size();
if (len < 4) return ans; // you want 4-sum, right?

/* idea: travers first and second numbers, then use o(n) to find third and fourth numbers

o(n) algorithm: when array is sorted, let c=0, d=len-1. if n[c]+n[d]<target, we know n[d] can never be
answer, since n[c] is alreayd smallest but the sum is still > target. similarly, when sum>target, c+=1.
*/

sort(nums.begin(), nums.end());

for (int a=0; a<len-3; next_diff(nums, a))
for (int b=a+1; b<len-2; next_diff(nums, b)) {

int c=b+1, d=len-1;
int tar=target-nums[a]-nums[b];

while (c<d) {
int sum=nums[c]+nums[d];
if (sum>tar)
prev_diff(nums, d);
else if (sum<tar)
next_diff(nums, c);
else {
vector<int> sub;
sub.push_back(nums[a]);
sub.push_back(nums[b]);
sub.push_back(nums[c]);
sub.push_back(nums[d]);
ans.push_back(sub);
prev_diff(nums, d);
next_diff(nums, c);
}
}
}
return ans;
}

/* to remove duplicate answers: */
void next_diff(vector<int>& nums, int& p) {
int val=nums[p++];
while (p<nums.size())
if (nums[p]==val) p++;
else break;
}

void prev_diff(vector<int>& nums, int& p) {
int val=nums[p--];
while (p>=0)
if (nums[p]==val) p--;
else break;
}
};``````

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