C++ प्रोग्राम: ठीक k तत्वों वाले सभी संभावित सबसेट उत्पन्न करना

यह C++ प्रोग्राम दिए गए सेट से ठीक k आकार के सभी संभावित सबसेट (उपसमुच्चय) उत्पन्न करता है। यह रिकर्सिव बैकट्रैकिंग का उपयोग करता है।

एल्गोरिदम

शुरुआत
  1. फंक्शन PossibleSubSet(char a[], int reqLen, int start, int currLen, bool check[], int len):
     - यदि currLen > reqLen तो लौटें
     - अन्यथा यदि currLen == reqLen तो नई जनरेटेड सीक्वेंस प्रिंट करें
     - यदि start == len तो लौटें (कोई और तत्व नहीं बचा)
     - प्रत्येक इंडेक्स के लिए दो विकल्प:
        * check[start] = true सेट करें और PossibleSubSet() को currLen+1 और start+1 के साथ रिकर्सिवली कॉल करें
        * check[start] = false सेट करें और PossibleSubSet() को केवल start+1 के साथ रिकर्सिवली कॉल करें
समाप्ति

उदाहरण कोड

#include <iostream>
using namespace std;

void PossibleSubSet(char a[], int reqLen, int start, int currLen, bool check[], int len) {
    if (currLen > reqLen) return;
    else if (currLen == reqLen) {
        cout << "\t";
        for (int i = 0; i < len; i++) {
            if (check[i] == true)
                cout << a[i] << " ";
        }
        cout << "\n";
        return;
    }
    if (start == len) return;
    
    check[start] = true;
    PossibleSubSet(a, reqLen, start + 1, currLen + 1, check, len);
    check[start] = false;
    PossibleSubSet(a, reqLen, start + 1, currLen, check, len);
}

int main() {
    int n, m;
    cout << "Enter the number of elements: ";
    cin >> n;
    
    char a[n];
    bool check[n];
    
    cout << "\n";
    for (int i = 0; i < n; i++) {
        cout << "Enter " << i+1 << " element: ";
        cin >> a[i];
        check[i] = false;
    }
    
    cout << "\nEnter the length of the subsets required: ";
    cin >> m;
    
    cout << "\nThe possible combinations of length " << m << " for the given array set:\n";
    PossibleSubSet(a, m, 0, 0, check, n);
    return 0;
}

आउटपुट

Enter the number of elements: 7
Enter 1 element: 7
Enter 2 element: 6
Enter 3 element: 5
Enter 4 element: 4
Enter 5 element: 3
Enter 6 element: 2
Enter 7 element: 1
Enter the length of the subsets required: 6

The possible combinations of length 6 for the given array set:
7 6 5 4 3 2
7 6 5 4 3 1
7 6 5 4 2 1
7 6 5 3 2 1
7 6 4 3 2 1
7 5 4 3 2 1
6 5 4 3 2 1

गणितीय पृष्ठभूमि: n तत्वों में से k तत्व चुनने के तरीकों की संख्या C(n,k) = n!/(k!(n-k)!) होती है। इस उदाहरण में C(7,6) = 7 कॉम्बिनेशन हैं।