Find All Permutations of the Letters in a Particular String

Permutations of string 'ABC' are:
ABC, ACB, BAC, BCA, CAB, CBA.

Taking the backtracking strategy, here is a solution. The program prints all permutation of the given string .It's assumed that NO same character in the string. So, the given string has same character, some redundant results are shown. You can avoid it by maintaining array to save permutations.

public static void main(String args[]) {
char[] input = {'A', 'B', 'C'};
permute(input, 0, input.length-1);
}

public static void swap(char[] str, int i, int j) {
char temp;

temp = str[j];
str[j] = str[i];
str[i] = temp;
}

public static void permute(char[] str, int start, int end) {
if (start == end)
System.out.println(str);
else {
for (int i=start; i<=end; i++) {
swap(str, start, i);
permute(str, start+1, end);
swap(str, start, i);
}
}
}

Posted in C, Google Interview Question, Java, MS interview Question, Permutation, Programming