aboutsummaryrefslogtreecommitdiff
path: root/4sum.cpp
diff options
context:
space:
mode:
Diffstat (limited to '4sum.cpp')
-rw-r--r--4sum.cpp48
1 files changed, 48 insertions, 0 deletions
diff --git a/4sum.cpp b/4sum.cpp
new file mode 100644
index 0000000..8ab5fa4
--- /dev/null
+++ b/4sum.cpp
@@ -0,0 +1,48 @@
+#include "leetcode.h"
+
+class Solution {
+public:
+ vector<vector<int>> fourSum(vector<int> &nums, int target) {
+ sort(begin(nums), end(nums));
+ return kSum(nums, target, 0, 4);
+ }
+
+ vector<vector<int>> kSum(vector<int> &nums, int target, int start, int k) {
+ vector<vector<int>> result;
+ if (start == nums.size())
+ return result;
+ int avgVal = target / k;
+ if (nums[start] > avgVal || avgVal > nums.back())
+ return result;
+ if (k == 2)
+ return twoSum(nums, target, start);
+ for (int i = start; i < nums.size(); ++i) {
+ if (i == start || nums[i - 1] != nums[i]) {
+ for (vector<int> &subset :
+ kSum(nums, static_cast<long>(target) - nums[i], i + 1, k - 1)) {
+ result.push_back({nums[i]});
+ result.back().insert(end(result.back()), begin(subset), end(subset));
+ }
+ }
+ }
+ return result;
+ }
+
+ vector<vector<int>> twoSum(vector<int> &nums, int target, int start) {
+ vector<vector<int>> result;
+ int low = start, high = nums.size() - 1;
+ while (low < high) {
+ int currSum = nums[low] + nums[high];
+ if (currSum < target || (low > start && nums[low] == nums[low - 1]))
+ ++low;
+ else if (currSum > target ||
+ (high < nums.size() - 1 && nums[high] == nums[high + 1]))
+ --high;
+ else
+ result.push_back({nums[low++], nums[high--]});
+ }
+ return result;
+ }
+};
+
+int main() {}