48 回溯算法求解活字印刷

问题描述：你有一套伙子字模titles，其中每个字模上都刻有一个字母tiles[i]。返回你可能印出的非空字母序列的数字。注意在本题中，每个活字字模只能使用一次。

例：输入"AAB"
解释：所有可能的序列为'A','B','AA','AB','BA','AAB','ABA','BAA'

DFS分析：由于模版中有重复，则可以首先对于模板进行排序，在选择时，如果上一个选择了某个重复的值，则可以继续选择，若上一个值没有选择，则不能进行选择，且每次可以选择或者不选两种情况，只能进行模板长度次选择，超过且当前不为空的情况下是一种已有的情况。

public void tranceBack(char tiles,Boolean used,String templist,int index,Integer all)
{
if(templist.length()!=0&&index==tiles.length)
{
all=all+1;
return;?
}
for(int i=0;i<titles.length;i++)
{
if(used[i]==false)
{
continue;
}else
{
if(tiles[i]==templist.charAt(templist.length()-1)&&used[i]==false)
{
continue;
}
//有选和不选两种情况
used[i]=true;
tranceBack(tiles,used,templist+tiles[i],index+1,all);
used[i]=false;
tranceBack(tiles,used,templist,index+1,all);
}
}
}
public int TranceBack(String tile)
{
Integer all=0;
char [] tiles=tile.toCharArray();
Boolean used[]=new Boolean[tile.length];
tranceBack(tiles,used,new String(""),0,all);
???????return all.parseInt();
}