Complementary task for topic: 10

M Nemeth � 2023-08-29 15:21:04.632218'

Recursion: combination

Write a program to print all possible combinations of a given string using recursion!
For example, given the input "abc", the program should print all combinations like "a", "b", "c", "ab", "ac", "bc", "abc".

Hint: That will be a fork recursion. We have to include and exclude all the characters once. So the solution will be something like that:
string="abc"
1st step combination("abc") and combination("bc")
| |
2.nd: [comb("abc") and comb("ac")] and [comb("bc") and comb("c)]
etc.
if we reach end of the string, print out! (base)

HELP:
the function declaration:
void printCombinations(char str[], int start, char combination[], int index);

Solution

#include 
#include 

// Function to print all combinations of a given string using recursion
void printCombinations(char str[], int start, char combination[], int index) {
    int length = strlen(str);
    
    // Base case: If the index has reached the end of the string, print the combination
    if (index == length) {
        combination[index] = '\0';
        printf("%s\n", combination);
        return;
    }
    
    // Include the character at the current index in the combination
    combination[index] = str[start];
    printCombinations(str, start + 1, combination, index + 1);
    
    // Exclude the character at the current index from the combination
    printCombinations(str, start + 1, combination, index);
}

int main() {
    char inputString[100];
    printf("Enter a string: ");
    scanf("%s", inputString);
    
    int length = strlen(inputString);
    char combination[length + 1]; // Array to store the combinations
    
    printf("All combinations of the string:\n");
    printCombinations(inputString, 0, combination, 0);
    
    return 0;
}

Explanation

The user inputs the string, and the program reads it using scanf.
The main function then calls the printCombinations function, passing the input string, start index (initialized to 0), an array to store combinations, and the current index (initialized to 0) as arguments.
The printCombinations function uses recursion to print all combinations of the given string. It has a base case where the index reaches the end of the string (index == length), at which point it prints the combination and returns. During recursion, it includes the character at the current index in the combination and makes the recursive call for the next index. It also makes another recursive call excluding the character at the current index from the combination, to explore all possible combinations.

< < previous next > >