public static ArrayList<String> getPerms(String str)
{
if(str==null)
return null;
ArrayList<String> permutations=new ArrayList<String>();
if(str.length()==0)//終止條件
{
permutations.add("");
return permutations;
}
char first=str.charAt(0);//取得第一個字元
String remainder=str.substring(1);//移除第一個字元
ArrayList<String> words=getPerms(remainder);
for(String word:words)
{
for(int j=0;j<=word.length();j++)
{
String s=insertCharAt(word,first,j);
permutations.add(s);
}
}
return permutations;
}
public static String insertCharAt(String word,char c,int i)
{
String start=word.substring(0,i);
String end=word.substring(i);
return start+c+end;
}
由于将會有N！種排列組合，這種解法的時間複雜度為O(n!)。