题目
https://leetcode.com/problems/4sum/description/
想法
跟昨天的那个combination sum应该差不多，回溯就可以了
唔 试了半天并不可以
有错误的代码：
答案
看了其他人的答案，发现没有用这种方式的，想必会超时吧
待研究…
这里并没有限制数的范围，如果用回溯的话，需要遍历剩余的的所有的数，那么将是O(n^2)的复杂度，不现实
18. 4Sum
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
public:
vector<vector<int>> ans;
void sumIt(vector<int> &curr, vector<int> &nums, int idx, int k, int target) {
if (k == 0 || idx == nums.size())
return;
if (nums[idx] == target && k == 1) {
curr.push_back(nums[idx]);
ans.push_back(curr);
curr.pop_back();
} else if (nums[idx] < target) {
if (k > 1) {
curr.push_back(nums[idx]);
sumIt(curr, nums, idx + 1, k - 1, target - nums[idx]);
curr.pop_back();
} else {
sumIt(curr, nums, idx + 1, k, target);
}
}
// curr.pop_back();
}
vector<vector<int>> fourSum(vector<int> &nums, int target) {
std::sort(nums.begin(), nums.end());
vector<int> curr;
sumIt(curr, nums, 0, 4, target);
return ans;
}
};