aboutsummaryrefslogtreecommitdiff
path: root/4sum.cpp
diff options
context:
space:
mode:
Diffstat (limited to '4sum.cpp')
-rw-r--r--4sum.cpp48
1 files changed, 0 insertions, 48 deletions
diff --git a/4sum.cpp b/4sum.cpp
deleted file mode 100644
index 8ab5fa4..0000000
--- a/4sum.cpp
+++ /dev/null
@@ -1,48 +0,0 @@
-#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() {}