Given an array nums of n integers, return an array of all the unique quadruplets [nums[a], nums[b], nums[c], nums[d]] such that:
0 <= a, b, c, d < n
a, b, c, and d are distinct.
nums[a] + nums[b] + nums[c] + nums[d] == target
You may return the answer in any order.
Example 1:
Input: nums = [1,0,-1,0,-2,2], target = 0
Output: [[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
Example 2:
Input: nums = [2,2,2,2,2], target = 8
Output: [[2,2,2,2]]
class Solution {
public:
vector<vector<int>> fourSum(vector<int> &nums, int target) {
unordered_set<int> seen;
set<multiset<int>> ans_set;
int n = size(nums);
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
for (int k = j + 1; k < n; k++) {
int lastNumber = target - (nums[i] + nums[j] + nums[k]);
if (seen.count(lastNumber))
ans_set.emplace(multiset<int>{nums[i], nums[j], nums[k], lastNumber});
}
}
seen.insert(nums[i]);
}
vector<vector<int>> ans(size(ans_set));
for_each(begin(ans_set), end(ans_set),[&, i(0)](auto &el) mutable { ans[i++] = vector<int>(begin(el), end(el)); });
return ans;
}
};
