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