In this article we will discuss how to print all permutations of a given String using Python programming Language.
Before diving into the program, let us first see what is a Permutation.
Permutation
A permutation is the rearrangement of the characters of a string. Let us take an example of the string “ABC”. Here the permutations of the respective string are ABC ACB BAC BCA CBA CAB.
Useful Links:
Below is the recursion tree using backtrack to find Permutations.
Program
Now let us see the Python Program to print all the permutations of a string.
Time Complexity
Now let us analyse the time complexity of the above backtracing algorithm used. Here the time taken to print a permutation is n as it has to travel down to the depth of n to print a permutation. No of permutations of a string of size n is n! Hence the total time to print all the permutations is O(n x n!)
