C++ में 4Sum समस्या

मान लीजिए हमारे पास संख्याओं की एक सरणी है। यह n पूर्णांकों को संग्रहीत करती है, सरणी में चार तत्व a, b, c और d हैं। हमारे पास एक और लक्ष्य मान है, जैसे कि a + b + c + d = लक्ष्य। सरणी में सभी अद्वितीय चौगुनी (quadruplets) ढूंढें जो स्थिति को संतुष्ट करते हैं। तो यदि सरणी [-1,0,1,2,0,-2] जैसी है और लक्ष्य 0 है, तो परिणाम [[-1, 0, 0, 1],[-2, -1, 1, 2], [-2, 0, 0, 2]] होगा।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• वास्तविक योग kSum() नामक फ़ंक्शन का उपयोग करके किया जा रहा है। यह सरणी, प्रारंभ, k और लक्ष्य लेता है। प्रारंभ में फ़ंक्शन को k मान 4 के साथ कॉल किया जाएगा। फ़ंक्शन निम्नानुसार होगा
• एक सरणी res परिभाषित करें
• यदि k = 2, तो
  • left := प्रारंभ और right := सरणी आकार - 1
  • आकार 2 की एक और सरणी temp परिभाषित करें
  • जब तक left < right
    • यदि arr[left] + arr[right] = लक्ष्य, तो
      • temp[0] := arr[left], temp[1] := arr[right], और temp को res में डालें
      • जब तक left < right और arr[left] = arr[left + 1]
        • l को 1 से बढ़ाएं
      • जब तक left < right और arr[right] = arr[right - 1]
        • r को 1 से घटाएं
      • l को 1 से बढ़ाएं और r को 1 से घटाएं
    • अन्यथा यदि arr[left] + arr[right] > लक्ष्य, तो right को 1 से घटाएं
    • अन्यथा left को 1 से बढ़ाएं
• अन्यथा
  • i को प्रारंभ से सरणी आकार - k तक की रेंज में
    • यदि i > प्रारंभ और arr[i] = arr[i - 1], तो अगले चरणों को छोड़ें और जारी रखें
    • एक 2D सरणी temp परिभाषित करें := kSum(arr, i + 1, k - 1, लक्ष्य - arr[i])
    • j को 0 से temp तक की रेंज में
      • arr[i] को temp[j] के बाद डालें
    • temp के सभी तत्वों को res में कॉपी करें
• res लौटाएं

उदाहरण (C++)

बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें -

#include <bits/stdc++.h> using namespace std; void print_vector(vector<vector<int> > v){    cout << "[";    for(int i = 0; i<v.size(); i++){       cout << "[";       for(int j = 0; j <v[i].size(); j++){          cout << v[i][j] << ", ";       }       cout << "],";    }    cout << "]"<<endl; } class Solution { public:    void addAll(vector < vector <int> >& res, vector < vector <int> >& temp){       for(int i = 0; i < temp.size(); i++)res.push_back(temp[i]);    }    vector<vector<int>> fourSum(vector<int>& nums, int target) {       sort(nums.begin(), nums.end());       return kSum(nums, 0, 4, target);    }    vector < vector <int> > kSum(vector <int>& arr, int start, int k, int target){       vector < vector <int> > res;       if(k == 2){          int left = start;          int right = arr.size() - 1;          vector <int> temp(2);          while(left < right){             if(arr[left] + arr[right] == target){                temp[0] = arr[left];                temp[1] = arr[right];                res.push_back(temp);                while(left < right && arr[left] == arr[left + 1])left++;                while(left < right && arr[right] == arr[right - 1])right--;                left++;                right--;             }             else if(arr[left] + arr[right] > target)right--;             else left ++;          }       }       else{          for(int i = start; i < (int)arr.size() - k + 1; i++){             if(i > start && arr[i] == arr[i - 1])continue;             vector < vector <int> > temp = kSum(arr, i + 1, k - 1, target - arr[i]);             for(int j = 0; j < temp.size(); j++){                temp[j].push_back(arr[i]);             }             addAll(res, temp);          }       }       return res;    } }; main(){    Solution ob;    vector<int> v = {1,0,-1,0,-2,2};    print_vector(ob.fourSum(v, 0)); }

इनपुट

[1,0,-1,0,-2,2] 0

आउटपुट

[[1,2,-1,-2],[0,2,0,-2],[0,1,0,-1]]