Permutations of a string

Question

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);
    }

  }

Answer 1

The number of permutations of n choose n items is always going to be n!. The way to optimize the solution is to prune the permutations to those that might solve the problem. This requires domain knowledge.

For example if the problem involves ordinary English words all permutations matching *qz* or *mA* can be eliminated.

Incidentally, \$O(n*n!)\$ can be shortened to \$O(n!)\$ since it is roughly \$O((n+1)!)\$