मान लीजिए हमारे पास संख्याओं का एक समूह है; हमें उस समूह के सभी संभावित सबसेट उत्पन्न करने हैं। इसे पावर सेट (power set) के नाम से भी जाना जाता है। हमें ध्यान रखना है कि तत्व डुप्लिकेट हो सकते हैं। यदि समूह [1,2,2] है, तो पावर सेट होगा [[], [1], [2], [1,2], [2,2], [1,2,2]]।
आइए चरण देखें:
- res नामक एक सरणी और x नामक एक सेट परिभाषित करें
- हम इसे रिकर्सिव दृष्टिकोण से हल करेंगे। यदि रिकर्सिव विधि का नाम solve() है, और यह इंडेक्स, एक अस्थायी सरणी, और संख्याओं की सरणी (nums) लेती है
- solve() फंक्शन इस तरह काम करेगा:
- यदि इंडेक्स = v का आकार, तो:
- यदि temp, x में मौजूद नहीं है, तो temp को res में डालें और x में भी डालें
- वापस करें
- solve(index + 1, temp, v) कॉल करें
- v[index] को temp में डालें
- solve(index + 1, temp, v) कॉल करें
- temp से अंतिम तत्व हटाएं
- यदि इंडेक्स = v का आकार, तो:
- मुख्य फंक्शन इस तरह होगा:
- res और x को क्लियर करें, और दी गई सरणी को सॉर्ट करें, एक temp सरणी परिभाषित करें
- solve(0, temp, सरणी) कॉल करें
- res सरणी को सॉर्ट करें और वापस करें
उदाहरण
#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;
}
};
int 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, ],]