HjHimansh

fourSum

Jan 15th, 2022
542
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. vector<vector<int>> fourNumbersSum(vector<int> nums, int targetSum){
  5.     if(nums.size() <= 3) {
  6.         return {{}};
  7.     }
  8.  
  9.     vector<vector<int>> answer;
  10.  
  11.     unordered_map<int, bool> hashMap;
  12.     hashMap[nums[nums.size()-1]] = true;
  13.     for(int k=nums.size()-2; k>=2; k--){
  14.         hashMap[nums[k+1]] = true;
  15.         // we have nums[k+1....nums.size()-1] in the hashMap
  16.         for(int j=k-1; j>=1; j--){
  17.             for(int i=j-1; i>=0; i--){
  18.                 // now we have a triplet nums[i], nums[j], nums[k]
  19.                 int sum = nums[i] + nums[j] + nums[k];
  20.                 if(hashMap.count(targetSum - sum)){
  21.                     answer.push_back({
  22.                         nums[i],
  23.                         nums[j],
  24.                         nums[k],
  25.                         targetSum-sum
  26.                     });
  27.                 }
  28.             }
  29.         }
  30.     }
  31.  
  32.     return answer;
  33.  
  34. }
  35.  
  36. int main(){
  37.     vector<int> arr = {7, 6, 4, -1, 1, 2};
  38.     vector<vector<int>> answer = fourNumbersSum(arr, 16);
  39.    
  40.  
  41.     return 0;
  42. }
  43.  
RAW Paste Data