Print all the permutations of a string

Code:

using System;

public class Test
{
    public static void Main()
    {
        string str = "Asif";
        
        Console.WriteLine("Input: " + str);
        
        Console.WriteLine("Output: ");
        new Test().Permutations(str,"");
    }

    public void Permutations(string str, string prefix)
  {
  if(str.Length == 0)
  {
  Console.WriteLine(prefix);
  }
 
  for(int i = 0; i < str.Length; i++)
{
string sPrefix = prefix + str.Substring(i,1);
string sString = str.Substring(0,i) + str.Substring(i+1);

Permutations(sString, sPrefix);
}
}

}

Output:

Input: Asif
Output: 
Asif
Asfi
Aisf
Aifs
Afsi
Afis
sAif
sAfi
siAf
sifA
sfAi
sfiA
iAsf
iAfs
isAf
isfA
ifAs
ifsA
fAsi
fAis
fsAi
fsiA
fiAs
fisA

Run Time: O(n!)