#include "s0018_4sum.hpp"

vector<vector<int>> S0018::fourSum(vector<int>& nums, int target) {
  int len = nums.size();
  if (len < 4) {
    return {};
  }
  vector<vector<int>> result{};
  sort(nums.begin(), nums.end());
  for (int i{1}; i < len - 2; i++) {
    for (int j = len - 2; j > i; j--) {
      for (int x{0}, y = len - 1; x < i && y > j;) {
        if (nums[x] + nums[y] + nums[i] + nums[j] > target) {
          y--;
        } else if (nums[x] + nums[y] + nums[i] + nums[j] < target) {
          x++;
        } else {
          vector<int> v = {nums[x], nums[i], nums[j], nums[y]};
          if (std::find(result.begin(), result.end(), v) == result.end()) {
            result.push_back(v);
          }
          x++;
        }
      }
    }
  }
  return result;
}