C प्रोग्राम: सरणी या लूप के बिना {1,2,3,...n} के सभी उपसमुच्चय प्रिंट करना

समस्या विवरण

एक धनात्मक पूर्णांक n दिया गया है, सेट {1, 2, 3, ..., n} के सभी उपसमुच्चय प्रिंट करें किसी सरणी या लूप का उपयोग किए बिना। केवल रिकर्सन अनुमत है।

उदाहरण

इनपुट: 3
आउटपुट: { 1 2 3 } { 1 2 } { 1 3 } { 1 } { 2 3 } { 2 } { 3 } { }

इनपुट: 4
आउटपुट: { 1 2 3 4 } { 1 2 3 } { 1 2 4 } { 1 2 } { 1 3 4 } { 1 3 } { 1 4 } { 1 } { 2 3 4 } { 2 3 } { 2 4 } { 2 } { 3 4 } { 3 } { 4 } { }

बिटमास्क दृष्टिकोण (रिकर्सिव)

कुल उपसमुच्चय = 2ⁿ। प्रत्येक उपसमुच्चय एक बिटमास्क (0 से 2ⁿ-1) से मेल खाता है।

n=3 के लिए:

C प्रोग्राम (केवल रिकर्सन)

#include <stdio.h>
#include <math.h>

// एक विशिष्ट बिटमास्क के लिए उपसमुच्चय प्रिंट करें
void print_subset(int bit, int num, int n) {
    if (bit >= 0) {
        if (num & (1 << bit))
            printf("%d ", n - bit);
        print_subset(bit - 1, num, n);
    }
}

// सभी उपसमुच्चय प्रिंट करें
void print_subsets(int n, int num) {
    if (num >= 0) {
        printf("{ ");
        print_subset(n - 1, num, n);
        printf("} ");
        print_subsets(n, num - 1);
    }
}

int main() {
    int n;
    printf("n दर्ज करें (1-10): ");
    scanf("%d", &n);
    
    if (n < 1 || n > 10) {
        printf("सीमा 1-10\n");
        return 1;
    }
    
    int total = (int)pow(2, n) - 1;
    print_subsets(n, total);
    printf("\n");
    return 0;
}

नमूना आउटपुट

n दर्ज करें: 3
{ 1 2 3 } { 1 2 } { 1 3 } { 1 } { 2 3 } { 2 } { 3 } { } 

कैसे काम करता है

1. print_subsets(n, 2ⁿ-1) से शुरू होता है
2. प्रत्येक कॉल के लिए:
   • "{ " प्रिंट करता है
   • print_subset को बिट्स जांचने के लिए कॉल करता है
   • "} " प्रिंट करता है
   • अगली छोटी संख्या के लिए रिकर्स करता है
3. बेस केस: जब num < 0 हो तो रुकें

जटिलता

• समय: O(n × 2ⁿ) - प्रत्येक उपसमुच्चय के लिए n बिट्स जांचता है
• स्थान: O(n) - रिकर्सन स्टैक गहराई
• कुल उपसमुच्चय: 2ⁿ

विकल्प: बैकट्रैकिंग दृष्टिकोण

void backtrack(int idx, int n, int *current, int len) {
    if (idx > n) {
        printf("{ ");
        for (int i = 0; i < len; i++) printf("%d ", current[i]);
        printf("} ");
        return;
    }
    // शामिल करें
    current[len] = idx;
    backtrack(idx + 1, n, current, len + 1);
    // बाहर करें
    backtrack(idx + 1, n, current, len);
}

// कॉल: int arr[10]; backtrack(1, n, arr, 0);