Given a string , print different permutations of the string
Points to remember :
- If we are going through all the permutations , it is going to take O(n!) time excluding all the other processing time
In place approach :
We keep lock the left side of the string and keep swapping the right parts.
Complexity =O(n! * n) (assuming the time to print is O(1) ) else it is O(n! *n) (where the extra O(n) is to print the permutation)
Using extra memory :
Complexity =O(n! * n) (assuming the time to print is O(1) ) else it is O(n! *n +O(n!*n) ie. the time create the new string (each erase operation is O(n) )+ time taken to print each of the permutation.
Backtracking Complexity example — https://www.geeksforgeeks.org/rat-in-a-maze-backtracking-2/?ref=lbp
