Given a string,the task is to print all the permutations of the string.
A permutation is a rearrangement of the elements of an ordered list S.A string of length N has N! permutations.
Let the string be S=”abc”.
Length of the string=3
Number of permutations=3!=6
All permutations of a string X is the same thing as all permutations of each possible character in X, combined with all permutations of the string X without that letter in it.
All permutations of “abcd” are-
“a” concatenated with all permutations of “bcd”.
“b” concatenated with all permutations of “acd”.
“c” concatenated with all permutations of “bad”.
“d” concatenated with all permutations of “bca”.
The first character is kept constant and permutations are generated with the rest.Then,the first two characters are kept constant and permutations are generated with the rest until we are out of characters.
This algorithm is performed on the input string itself.Thus,no additional memeory is required.The “backtracking” undoes the changes to the string, leaving it in its original state.
//to swap characters at position i and j
void swap (int i, int j)
temp = a[i];
a[i] = a[j];
a[j] = temp;
//i is the starting index
//n is the ending index
//initially,permute(0,n-1) is called
void permute(int i, int n)
if (i == n)
for (j = i; j <= n; j++)
//increasing the number of fixed characters
It has a time complexity of O(N*N!) and is an example of Backtracking.