4Sum Algorithm
The 4Sum Algorithm is a popular computational problem in computer science that aims to find all the unique quadruplets (four elements) in a given integer array that sum up to a target value. This algorithm can be considered an extension of the more common 2Sum and 3Sum problems, which focus on pairs and triplets, respectively. The problem statement is defined as follows: given an array of n integers and a target value, find all unique quadruplets a, b, c, and d such that a + b + c + d = target. The output of the algorithm should be a list of all unique combinations (a, b, c, d) that meet the target sum, with each combination sorted in ascending order. A key constraint of the problem is that the resulting list of combinations should not contain duplicate quadruplets.
A common approach to solving the 4Sum problem is by using a variation of the sorting and two-pointer technique, which is also used in the 3Sum problem. First, the given array is sorted in ascending order. Then, two nested loops are used to iterate through the array, with each iteration fixing two elements of the quadruplet, say a and b. For the remaining two elements, c and d, a two-pointer method is employed, where one pointer is initialized at the position right after b and the other pointer is initialized at the end of the array. The two pointers move towards each other while searching for a valid pair of elements that satisfy the target sum condition. To avoid duplicate quadruplets, the algorithm should also include checks to skip over any repeated elements during the iteration. The overall time complexity of this approach is O(n^3), where n is the number of elements in the array. Another approach to the 4Sum problem is by using a hash table to store the possible pairs and their sums, which can improve the time complexity to O(n^2), but at the cost of increased space complexity.
struct twoSum {
int lf, rt, val;
twoSum(int _lf, int _rt, int _val)
: lf(_lf), rt(_rt), val(_val) { }
friend bool operator < (const twoSum& lhs, const twoSum& rhs) {
return lhs.val < rhs.val;
}
};
class Solution {
public:
vector<vector<int>> fourSum(vector<int>& num, int target) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
vector<vector<int>> result;
vector<twoSum> twosums;
for (int i = 0; i < num.size(); i++) {
for (int j = i + 1; j < num.size(); j++)
twosums.push_back(twoSum(i, j, num[i]+num[j]));
}
sort(twosums.begin(), twosums.end());
int n = twosums.size();
for (int i = 0; i < n; i++) {
int value = target - twosums[i].val;
int lf = find_lower_bound(twosums, i + 1, n - 1, value);
int rt = find_upper_bound(twosums, i + 1, n - 1, value);
for (int j = lf; j <= rt; j++) {
if (twosums[i].lf == twosums[j].lf) continue;
if (twosums[i].rt == twosums[j].lf) continue;
if (twosums[i].lf == twosums[j].rt) continue;
if (twosums[i].rt == twosums[j].rt) continue;
vector<int> four;
four.push_back(num[twosums[i].lf]);
four.push_back(num[twosums[i].rt]);
four.push_back(num[twosums[j].lf]);
four.push_back(num[twosums[j].rt]);
sort(four.begin(), four.end());
if (find(result.begin(), result.end(), four) == result.end())
result.push_back(four);
}
}
return move(result);
}
int find_lower_bound(vector<twoSum>& twosums, int l, int r, int val) {
while (l <= r) {
int m = (l + r) / 2;
if (twosums[m].val >= val)
r = m - 1;
else
l = m + 1;
}
return r + 1;
}
int find_upper_bound(vector<twoSum>& twosums, int l, int r, int val) {
while (l <= r) {
int m = (l + r) / 2;
if (twosums[m].val <= val)
l = m + 1;
else
r = m - 1;
}
return l - 1;
}
};
