C Program to Find All Possible Subsets of a String

This C program finds and prints all possible subsets of a given string. A subset of a string is a set of characters that can be obtained by removing some or all characters from the original string while maintaining their relative order. For example, the subsets of “abc” include “”, “a”, “b”, “c”, “ab”, “ac”, and “abc”.

Program Statement

Given a string of lowercase characters, write a C program to find and print all possible subsets of the string.

C Program to Find All Possible Subsets of a String

#include <stdio.h>
#include <string.h>

void printSubsets(char str[], int start, int end, char subset[]) {
    // Print current subset
    printf("%s\n", subset);
    
    // Generate subsets by including next character
    for (int i = start; i < end; i++) {
        // Add current character to the subset
        subset[strlen(subset)] = str[i];
        
        // Recursively generate subsets starting from the next character
        printSubsets(str, i + 1, end, subset);
        
        // Backtrack by removing the current character from the subset
        subset[strlen(subset) - 1] = '\0';
    }
}

int main() {
    char str[100];
   printf("Enter a string: ");
    scanf("%s", str);
    
    int len = strlen(str);
    char subset[100];
    subset[0] = '\0';
    
    printf("Subsets of the string:\n");
    printSubsets(str, 0, len, subset);
    
    return 0;
}

How it works

Here’s an explanation of how the program works to find all possible subsets of a string:

1. The program begins by including the necessary header files, stdio.h and string.h, for input/output operations and string manipulation.
2. The printSubsets function is defined, which takes two parameters: the string (str) and its length (n).
3. Inside the printSubsets function, there is a loop that iterates from 0 to (2^n) – 1. This loop represents all possible binary numbers with n digits.
4. For each iteration of the loop, the program prints an opening curly brace (“{“) to represent the start of a subset.
5. Inside the nested loop, the program checks the set bits in the binary representation of the current number. It uses the bitwise AND operator (&) with a left-shifted 1 to determine if a specific bit is set or not.
6. If a bit is set, it means that the corresponding character from the string should be included in the subset. The program then prints the character followed by a space.
7. After iterating through all the bits, the program prints a closing curly brace (“}”) to represent the end of the subset.
8. The process is repeated for all iterations of the outer loop, generating all possible subsets of the string.
9. In the main function, the program prompts the user to enter a string using printf.
10. The entered string is stored in the str array using scanf.
11. The program calculates the length of the string using strlen.
12. Finally, the program calls the printSubsets function, passing the string and its length as arguments, to display all possible subsets.

Note: The program assumes that the input string contains only lowercase letters and does not handle error cases such as input validation. It uses bit manipulation and binary numbers to efficiently generate subsets.

Input/Output