51 N皇后

n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。

给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。

每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。

class Solution {
    int n;
    List<List<String>> ret =new LinkedList<>();
    public List<List<String>> solveNQueens(int n) {
        this.n=n;
        char[][] board=new char[n][n];
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                board[i][j]='.';
            }
        }
        backtrack(board,0);
        return ret;
    }

    void backtrack(char[][] board,int begain){
        if(begain==n){//递归出口，即找到了一条满足条件的路
            LinkedList<String> track=new LinkedList<>();
            for(int i=0;i<n;i++){
                String s=String.copyValueOf(board[i]);//把此时的棋盘copy到返回值中
                track.add(s);
            }
            ret.add(track);
            return;
        }

        if(begain<n){
            for(int i=0;i<n;i++){
                if(!isValid(board,begain,i)){//判断要不要进行递归，即如果执行board[begain][i]='Q'，有没有违反条件
                    continue;//如果违反，换下一个值；如果都违反，则返回上一次递归了
                }
                board[begain][i]='Q';//这是这一次递归的操作
                backtrack(board,begain+1);//进入递归，参数增1
                board[begain][i]='.';//回溯之后，记得要回滚之前的操作
            }
        }
        
    }

    public Boolean isValid(char[][] board,int begain,int i){
        if(begain-1>=0){
            //检查上方
            for(int up=begain-1;up>=0;up--){
                if(board[up][i]=='Q'){
                    return false;
                }
            }
            //检查左上方
            for(int left=i-1,j=begain-1;left>=0&&j>=0;left--,j--){
                if(board[j][left]=='Q')
                    return false;
            }
            //检查右上方
            for(int right=i+1,j=begain-1;right<n&&j>=0;right++,j--){
                if(board[j][right]=='Q')
                    return false;
            }
        }
        return true;
    }
}

使用回溯法，回溯法（探索与回溯法）是一种选优搜索法，又称为试探法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。

回溯法说白了是一种暴力搜索法，其原理和深度优先搜索很像，只不过要考虑选不选的问题，其时间复杂度都较高，通常是n！空间复杂度是n。（对于排列组合、集合的问题适合）

1 出口

回溯法一般都会用到递归，递归的出口条件放在何处很重要，一般放在递归函数的入口，即每次递归前都要判断一下是不是满足终止条件；还有走不通的条件，要放在递归的入口，判断到底要不要进行递归

（题中出口即begin==n的判断，到达这里就证明找到了一条通路；走不通的条件是isValid函数，它来决定要不要进入递归）

2 递归的参数

进入新一轮递归时，参数要改变；如果此条路走不通了，就要回到上一轮递归，而且最好回滚这一轮递归的操作，以免对后面走另外一条路时产生影响

递归当中的处理：要视情况而定，要考虑选择，或者不选

46 全排列

给定一个 没有重复 数字的序列，返回其所有可能的全排列。

示例:

输入: [1,2,3]
输出:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]

class Solution {

    List<List<Integer>> ret=new ArrayList<>();

    public List<List<Integer>> permute(int[] nums) {
        ArrayList<Integer> track=new ArrayList<>();
        backtrack(nums,track);
        return ret;
    }

    void backtrack(int[] nums,ArrayList<Integer> track){
        if(track.size()==nums.length){
            ret.add(new ArrayList(track));//这里要注意，如果不新建，传入的是映射空值
            return;
        }
        for(int i=0;i<nums.length;i++){
            if(track.contains(nums[i])){//contains操作时O(n)的复杂度
                continue;
            }
            track.add(nums[i]);
            backtrack(nums,track);
            track.remove(track.size()-1);//撤销操作
        }
    }
}