Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> C++

C++ में सबसेट II (Subsets II)


मान लीजिए हमारे पास संख्याओं का एक समूह है; हमें उस समूह के सभी संभावित सबसेट उत्पन्न करने हैं। इसे पावर सेट (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 से अंतिम तत्व हटाएं
  • मुख्य फंक्शन इस तरह होगा:
    • 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, ],]
  1. - C++ में vector::resize() और vector::reserve() का अंतर

    वेक्टर में डायनामिक ऐरे की तरह खुद को ऑटोमैटिकली रीसाइज़ करने की क्षमता होती है। जब कोई एलिमेंट डाला या हटाया जाता है, तो कंटेनर अपने स्टोरेज को ऑटोमैटिकली संभालता है। vector::resize() और vector::reserve() के बीच मुख्य अंतर यह है कि resize() वेक्टर का साइज़ बदलने के लिए उपयोग किया जाता है जबकि rese

  1. - C++ में टाइप इन्फरेंस (प्रकार निगमन)

    टाइप इन्फरेंस या डिडक्शन का अर्थ है प्रोग्रामिंग भाषा में एक एक्सप्रेशन के डेटा टाइप का ऑटोमैटिक डिटेक्शन। यह कुछ स्ट्रॉन्गली स्टैटिकली टाइप्ड भाषाओं में मौजूद एक विशेषता है। C++ में, auto कीवर्ड (C++11 में जोड़ा गया) ऑटोमैटिक टाइप डिडक्शन के लिए उपयोग किया जाता है। उदाहरण के लिए, आप एक वेक्टर पर पु

  1. - पायथन में सबसेट्स (पावर सेट)

    मान लीजिए हमारे पास संख्याओं का एक सेट है; हमें उस सेट के सभी संभावित सबसेट उत्पन्न करने हैं। इसे पावर सेट के रूप में भी जाना जाता है। इसलिए यदि सेट [1,2,3] जैसा है, तो पावर सेट [[], [1], [2], [3], [1,2], [1,3], [2,3], [1,2,3]] होगा। आइए चरण देखते हैं - हम इसे रिकर्सिव दृष्टिकोण का उपयोग करके हल कर