I wrote the following code to permute the characters of a string assuming there is no repeated character.
I also want to make sure the space complexity of this algorithm is \$O(n*n!)\$: There are \$n!\$ recursive calls, for each of these calls, I copy a string of size \$n\$. Am I right?
Time complexity: \$O(n!)\$: \$n!\$ recursive calls
Is it possible to make it more efficient?
public static void permute(String str, String prefix){
if (str.length() == 0) System.out.println(prefix);
for (int i = 0; i < str.length(); i++){
String c = Character.toString(str.charAt(i));
String rest = str.substring(0, i) + str.substring(i+1);
permute(rest, prefix + c);
}
}
