输入一个字符串打印出这个字符串的全排列，剑指上面是字符串没有重复字母的，牛客上面输入有重复字母，要求搞掉重复的排列，还有顺序要求....嗯，其实区别不是很大，就按牛客上的来写。
Permutation递归产生所有前缀是charArray[0,begin-1]，后缀是charArray[begin,length-1]的全排列的所有排列。
public class Solution {
ArrayList<String> ans = new ArrayList<>();
public ArrayList<String> Permutation(String str) {
if(str == null || str.length() == 0){
return ans;
}
Permutation(str.toCharArray(),0);
Collections.sort(ans);
return ans;
}
private void swap(char[] charArray, int i, int j){
char tmp = charArray[i];
charArray[i] = charArray[j];
charArray[j] = tmp;
}
private void Permutation(char[] charArray, int begin){
if(begin == charArray.length){
String newString = new String(charArray);
if(!ans.contains(newString))
ans.add(newString);
return ;
}
for(int i = begin; i < charArray.length; i ++){
swap(charArray, i, begin);
Permutation(charArray, begin + 1);
swap(charArray, i, begin);//这块记得换回来
}
}
}
当然contains和sort那两步，完全可以使用TreeSet来解决问题。最后返回用ArrayList的参数是Collection的那个构造函数。
全排列问题一个更有名的问题就是n皇后问题。n*n的格子里头，每个皇后必然在不同行，我们用一个ColumnIndex[n]数组，ColumnIndex[i]表示第i行皇后所在的列，那就对0 1 2 3 4 5 6 7 8.....n-1（行列标从0开始）进行全排列，对于全排列的每个排列，去检查有没有两两皇后在某个对角线上面，也就是检查ColumnIndex[i] - ColumnIndex[j] == i - j就可以了，也就是在递归终止条件那块写个方法，检查一下这个ColumnIndex数组就好了。
