class Solution {
 public:
  vector<int> twoSum(vector<int>& nums, int target) {
    const int n = nums.size();
    for (int i = 0; i < n - 1; i++) {
      for (int j = i + 1; j < n; j++) {
        if (nums[i] + nums[j] == target) {
          return vector<int>{i, j};
        }
      }
    }
    throw "no combination";
  }
};

class Solution {
 public:
  vector<int> twoSum(vector<int>& nums, int target) {
    const int n = nums.size();
    unordered_map<int, int> m;
    for (int i = 0; i < n; i++) {
      const int complement = target - nums[i];
      if (m.find(complement) != m.end()) {
        return vector<int>{m[complement], i};
      }
      m[nums[i]] = i;
    }
    throw "no combination";
  }
};

class Solution {
 public:
  vector<int> twoSum(vector<int>& numbers, int target) {
    int l = 0;
    int r = numbers.size() - 1;
    while (l < r) {
      const int sum = numbers[l] + numbers[r];
      if (sum == target) {
        return vector<int>{l + 1, r + 1};
      } else if (sum < target) {
        l++;
      } else {
        r--;
      }
    }
    throw "no combination";
  }
};

class Solution {
  int twoSumSmaller(vector<int> &nums, int start, int target) {
    int count = 0;
    int l = start;
    int r = nums.size() - 1;
    while (l < r) {
      int sum = nums[l] + nums[r];
      if (sum >= target) {
        r--;
        continue;
      }
      count += r - l;
      l++;
    }
    return count;
  }

 public:
  int threeSumSmaller(vector<int> &nums, int target) {
    int count = 0;
    sort(nums.begin(), nums.end());
    const int n = nums.size();
    for (int i = 0; i < n; i++) {
      count += twoSumSmaller(nums, i + 1, target - nums[i]);
    }
    return count;
  }
};

class Solution {
  vector<vector<int>> kSum(vector<int> &nums, int k, int start, int target) {
    const int n = nums.size();
    vector<vector<int>> results;
    if (k == 2) {
      // two sum
      int l = start;
      int r = n - 1;
      while (l < r) {
        const int sum = nums[l] + nums[r];
        if (sum < target || (start < l && nums[l] == nums[l - 1])) {
          l++;
        } else if (target < sum || (r < n - 1 && nums[r] == nums[r + 1])) {
          r--;
        } else {
          results.push_back(vector<int>{nums[l], nums[r]});
          l++;
          r--;
        }
      }
      return results;
    }
    for (int i = start; i <= n - k; i++) {
      if (i > start && nums[i - 1] == nums[i]) {
        continue;
      }
      for (auto result : kSum(nums, k - 1, i + 1, target - nums[i])) {
        result.insert(result.begin(), nums[i]);
        results.push_back(result);
      }
    }

    return results;
  }

 public:
  vector<vector<int>> fourSum(vector<int> &nums, int target) {
    sort(nums.begin(), nums.end());
    auto results = kSum(nums, 4, 0, target);
    return results;
  }
};