I am learning backtracking and recursion and I am stuck at an algorithm for printing all the permutations of a string. I solved it using the bell algorithm for permutation but I am not able to understand the recursion method. I searched the web and found this code:
void permute(char *a, int i, int n)
if (i == n)
for (j = i; j <= n; j++)
permute(a, i+1, n);
The algorithm basically works on this logic:
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.
That is to say, all permutations of "abcd" are
This algorithm in particular instead of performing recursion on substrings, performs the recursion in place on the input string, using up no additional memory for allocating substrings. The "backtracking" undoes the changes to the string, leaving it in its original state.