aboutsummaryrefslogtreecommitdiff
path: root/4sum.cpp
blob: 8ab5fa414ddce72f7953709a0473bd3f8aaed483 (plain)
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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
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() {}