Backtracking question asked in Samsung and Amazon - Write a program to print all permutations of a given string.

Backtracking question asked in Samsung and Amazon - Write a program to print all permutations of a given string.

A permutation, also called an “arrangement number” or “order,” is a rearrangement of the elements of an ordered list S into a one-to-one correspondence with S itself. A string of length n has n! permutation.

Below are the permutations of string ABC.

ABC ACB BAC BCA CBA CAB

Solution based on backtacking:

Sample Program:


public class PermutationTest
{
public static void main(String[] args)
{
String str = "ABC";
int n = str.length();
PermutationTest permutation = new PermutationTest();
permutation.permute(str, 0, n-1);
}
private void permute(String str, int l, int r)
{
if (l == r)
System.out.println(str);
else
{
for (int i = l; i <= r; i++)
{
str = swap(str,l,i);
permute(str, l+1, r);
str = swap(str,l,i);
}
}
}

public String swap(String a, int i, int j)
{
char temp;
char[] charArray = a.toCharArray();
temp = charArray[i] ;
charArray[i] = charArray[j];
charArray[j] = temp;
return String.valueOf(charArray);
}

}

Output:

ABC
ACB
BAC
BCA
CBA
CAB


Time Complexity: O(n*n!) Note that there are n! permutations and it requires O(n) time to print a a permutation.

Note : The above solution prints duplicate permutations if there are repeating characters in input string.