// check if the values of the index pair same
bool samePairValues(pii x, pii y, vector<int>& nums) {
	if (nums[x.first] == nums[y.first] && nums[x.second] == nums[y.second])
		return true;
	return false;
}

// check if the index pairs are unique
bool isUnique(pii x, pii y) {
	if (x.first == y.first || x.second == y.second)
		return false;
	if (x.first == y.second || x.second == y.first)
		return false;
	return true;
}

vector<vector<int>> fourSum(vector<int> nums, int target) {

	sort(nums.begin(), nums.end());

	unordered_map<int, vector<pii>> pair_sums;
	int n = nums.size();
	for (int i = 0; i<n; ++i)
		for (int j = i + 1; j<n; ++j)
		{
			int this_pair_sum = nums[i] + nums[j];
			pii this_pair = make_pair(i, j);

			auto it = pair_sums.find(this_pair_sum);
			// check if there are more than 2 pair sums with the elements having the same values
			int count = 0;
			if (it != pair_sums.end()) {
				for (auto pair = it->second.begin(); pair != it->second.end(); ++pair)
					if (samePairValues(this_pair, *pair, nums))
						count++;
			}
			if (count < 2)
				pair_sums[this_pair_sum].push_back(this_pair);   // i < j AND nums[i] < nums[j], as the array is sorted
		}

	vector<vector<int>> res;

	for (auto it = pair_sums.begin(); it != pair_sums.end(); ++it)
	{
		int this_pair_sum = it->first;
		int other_pair_sum = target - this_pair_sum;

		auto other_it = pair_sums.find(other_pair_sum);
		if (other_it == pair_sums.end()) continue;

		for (auto this_pair = it->second.begin(); this_pair != it->second.end(); ++this_pair) {
			for (auto other_pair = other_it->second.begin(); other_pair != other_it->second.end(); ++other_pair) {
				if (isUnique(*this_pair, *other_pair) && this_pair->second < other_pair->first) {
					vector<int> sol({ nums[this_pair->first], nums[this_pair->second], nums[other_pair->first], nums[other_pair->second] });
					for (auto x : sol)
						cout << x << "\t";
					cout << endl;
					res.push_back(sol);
				}
			}
		}
		other_it->second.clear();
		it->second.clear();
	}

	return res;
}