fourSum

#include<bits/stdc++.h>
using namespace std;

vector<vector<int>> fourNumbersSum(vector<int> nums, int targetSum){
    if(nums.size() <= 3) {
        return {{}};
    }

    vector<vector<int>> answer;

    unordered_map<int, bool> hashMap;
    hashMap[nums[nums.size()-1]] = true;
    for(int k=nums.size()-2; k>=2; k--){
        hashMap[nums[k+1]] = true;
        // we have nums[k+1....nums.size()-1] in the hashMap
        for(int j=k-1; j>=1; j--){
            for(int i=j-1; i>=0; i--){
                // now we have a triplet nums[i], nums[j], nums[k]
                int sum = nums[i] + nums[j] + nums[k];
                if(hashMap.count(targetSum - sum)){
                    answer.push_back({
                        nums[i],
                        nums[j],
                        nums[k],
                        targetSum-sum
                    });
                }
            }
        }
    }

    return answer;

}

int main(){
    vector<int> arr = {7, 6, 4, -1, 1, 2};
    vector<vector<int>> answer = fourNumbersSum(arr, 16);


    return 0;
}