全排列 n皇后

输入一个字符串打印出这个字符串的全排列，剑指上面是字符串没有重复字母的，牛客上面输入有重复字母，要求搞掉重复的排列，还有顺序要求....嗯，其实区别不是很大，就按牛客上的来写。
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数组就好了。