मान लीजिए कि हमारे पास उम्मीदवार संख्याओं का एक सेट है (सभी तत्व अद्वितीय हैं) और एक लक्ष्य संख्या है। हमें उम्मीदवारों में सभी अद्वितीय संयोजन खोजने होंगे जहां उम्मीदवार संख्या दिए गए लक्ष्य के योग हो। उम्मीदवारों में से एक ही नंबर को एक से अधिक बार नहीं चुना जाएगा। इसलिए यदि तत्व [2,3,6,7,8] हैं और लक्ष्य मान 8 है, तो संभावित आउटपुट [[2,6],[8]]
होगाआइए चरणों को देखें -
- हम इसे पुनरावर्ती तरीके से हल करेंगे। पुनरावर्ती फ़ंक्शन को हल () के रूप में नामित किया गया है। यह अनुक्रमणिका, एक सरणी a, पूर्णांक b और एक अन्य सरणी अस्थायी लेता है। हल करने का तरीका नीचे की तरह काम करेगा -
- खाली सरणी रेस परिभाषित करें
- यदि b =0 है, तो रेज में अस्थायी डालें और वापस लौटें
- यदि अनुक्रमणिका =आकार a, तो वापस लौटें
- अगर b <0, तो वापस आएं
- सरणी को क्रमबद्ध करें एक
- एक के आकार के सूचकांक में i के लिए - 1
- यदि i> अनुक्रमणिका और a[i] =a[i – 1], तो जारी रखें
- अस्थायी में [i] डालें
- हल करें(i + 1, a, b - a[i], temp)
- अस्थायी से अंतिम तत्व हटाएं
- इंडेक्स =0, एरे ए, और टारगेट बी, और एक अन्य एरे टेम्प को पास करके सॉल्व () मेथड को कॉल करें
- रिटर्न रेस
आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -
उदाहरण
#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:
vector < vector <int> > res;
void solve(int idx, vector <int> &a, int b, vector <int> temp){
if(b == 0){
res.push_back(temp);
return;
}
if(idx == a.size())return;
if(b < 0)return;
sort(a.begin(), a.end());
for(int i = idx; i < a.size(); i++){
if(i > idx && a[i] == a[i-1])continue;
temp.push_back(a[i]);
solve(i + 1, a, b - a[i], temp);
temp.pop_back();
}
}
vector<vector<int> > combinationSum2(vector<int> &a, int b) {
res.clear();
vector <int> temp;
solve(0, a, b, temp);
return res;
}
};
main(){
Solution ob;
vector<int> v = {2,3,6,7,8};
print_vector(ob.combinationSum2(v, 10)) ;
} इनपुट
[2,3,6,7,8] 8
आउटपुट
[[2, 8, ],[3, 7, ],]