# My solution is not very fast, 32ms, but it's universal for nSum problems, and easy to understand!

• This is the first version which costs 152ms.

``````void nSum(vector<int>& nums, int target, int n, vector<vector<int>>& ans, vector<int>& res, int start, int len) {
if (n == 0) {
if (target == 0)
ans.push_back(res);
return;
}
for (int i = start;i <= len - n;++i) {
if (nums[i] * n > target || nums.back() * n < target)
break;
res.push_back(nums[i]);
nSum(nums,target-nums[i],n-1,ans,res,i+1,len);
res.pop_back();
while (i+1 <= len - n && nums[i] == nums[i+1])
++i;
}
}

vector<vector<int>> fourSum(vector<int>& nums, int target) {
vector<vector<int>> ans;
vector<int> res;
sort(nums.begin(),nums.end());
nSum(nums,target,4,ans,res,0,nums.size());
return ans;
}
``````

This is the second version, much faster, 32ms! I believe it can be optimized to run faster!

``````void nSum(vector<int>& nums, int target, int n, vector<vector<int>>& ans, vector<int>& res, int start, int len) {
if (n == 1) {
if (binary_search(nums.begin()+start,nums.end(),target)) {
res.push_back(target);
ans.push_back(res);
res.pop_back();
}
return;
}
for (int i = start;i <= len - n;++i) {
if (nums[i] * n > target || nums.back() * n < target)
break;
res.push_back(nums[i]);
nSum(nums,target-nums[i],n-1,ans,res,i+1,len);
res.pop_back();
while (i+1 <= len - n && nums[i] == nums[i+1])
++i;
}
}

vector<vector<int>> fourSum(vector<int>& nums, int target) {
vector<vector<int>> ans;
vector<int> res;
sort(nums.begin(),nums.end());
nSum(nums,target,4,ans,res,0,nums.size());
return ans;
}
``````

I always love this kind of easy code, my coding style is programming different problems in a common paradigm, and this one is simple standard backtracking with pruning!

• The code for turning is not right. Suppose you have {-6,-4,-3,-1,2,5,8}.
The first two operands is {-6,-1}, you get the last two operands by recursing with value of {2,5}.
When the first two operands is {-3,-4}, you get the last two operands still by recursing with value of {2,5}, which would waste a lot of time if there are n operands, and result in exceeding time. It is better idea to have a hashmap to store the value returned by recursing.

• This is indeed a pretty neat solution. However, it fails to pass 3Sum due to Time Limit Exceeded. I guess there might be no any large testcase for 4Sum to expose this issue.

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