C++ Recursion: Generating all permutations of a string with recursive function

Last update on December 20 2024 12:31:32 (UTC/GMT +8 hours)

Write a C++ program to implement a recursive function to generate all permutations of a given string.

Sample Solution:

C Code:

// Recursive function to generate all permutations of a string
#include <iostream>

#include <string>

// Function to generate all permutations of a string
void generate_Permutations(std::string text, int left, int right) {
  // Base case: if left and right indices are the same, we have a complete permutation
  if (left == right) {
    std::cout << text << std::endl; // Output the generated permutation
    return;
  }

  // Recursive case: swap each character with the character at the left index,
  // and recursively generate permutations for the rest of the string
  for (int i = left; i <= right; i++) {
    std::swap(text[left], text[i]); // Swap characters
    generate_Permutations(text, left + 1, right); // Recursively generate permutations
    std::swap(text[left], text[i]); // Backtrack by swapping back the characters
  }
}

int main() {
  std::string text;
  std::cout << "Input a string: ";
  std::cin >> text;

  std::cout << "All permutations of the string: " << std::endl;
  generate_Permutations(text, 0, text.length() - 1); // Generate permutations

  return 0;
}

Sample Output:

Input a string: abc
All permutations of the string:
abc
acb
bac
bca
cba
cab

Input a string: JS
All permutations of the string:
JS
SJ

Flowchart:

CPP Code Editor:

Contribute your code and comments through Disqus.

Previous C++ Exercise: Counting occurrences of an element in an array with recursive function.
Next C++ Exercise: Calculating product of two numbers without multiplication operator.