A string s is given, the task is to print all the permutations of s using recursion.
A string of length n has n! permutation.
Example 1: Print all permutations of "abc".
Input: "abc"
Output:
abc acb bac bca cba cab
Example 2: Print all permutations of "xyzd".
Input: "xyzd"
Output:
xyzd xydz xzyd xzdy xdzy xdyz yxzd yxdz yzxd yzdx ydzx ydxz zyxd zydx zxyd zxdy zdxy zdyx dyzx dyxz dzyx dzxy dxzy dxyz
Solutions
Method 1: Recursion & Swapping
In this solution we can get all the permutations using recursion while swapping character at index with all the character after it in the string.
Once the string is completely traversed (index at last element) we print the swapped string - base condition.
package com.cb.recursion;
/*
* Recursion + Swapping
* */
public class R12_PermutationsOfString {
public static void printPermutations(String s, int index) {
// print if index is at last element
// no more element to the right for swapping
if (index >= s.length() - 1) {
System.out.println(s);
return;
}
// swap with self and elements after current index
for (int i = index; i < s.length(); i++) {
printPermutations(swap(s, index, i), index + 1);
}
}
private static String swap(String s, int i, int j) {
char[] chars = s.toCharArray();
char c = chars[i];
chars[i] = chars[j];
chars[j] = c;
return new String(chars);
}
public static void main(String[] args) {
printPermutations("abc", 0);
}
}
abc acb bac bca cba cab
Complexity
There are n! permutations and it requires O(n) time to print a permutation so Time Complexity is O(n*n!).