什么是回溯法

• 回溯算法本质就是一个暴力枚举的思路（动态是求最值这个类型，是有选择的枚举，具有重叠结构，和最优子结构）
• 穷举的过程就遍历一颗多叉树的过程
• 回溯算法实际上一个类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解 条件时，就“回溯”返回，尝试别的路径。
• 回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点 称为“回溯点”。也可以称为剪枝点，所谓的剪枝，指的是把不会找到目标，或者不必要的路径裁剪掉。
• 许多复杂的，规模较大的问题都可以使用回溯法，有“通用解题方法”的美称。
• 在包含问题的所有解的解空间树中，按照深度优先搜索的策略，从根结点出发深度探索解空间树。当探索到某一结点时，要先判断该结点是否包含问题的解，如果包含，就从该结点出发继续探索下去，如果该结点不包含问题的解，则逐层向其祖先结点回溯。（其实回溯法就是对隐式图的深度优先搜索算法）。
• 若用回溯法求问题的所有解时，要回溯到根，且根结点的所有可行的子树都要已被搜索遍才结束。 而若使用回溯法求任一个解时，只要搜索到问题的一个解就可以结束。
• 除过深度优先搜索，常用的还有广度优先搜索。

全排列问题 

 

class Solution {
     List> res=new LinkedList<>();
    public List> permute(int[] nums) {
        LinkedListtrack=new LinkedList<>();
        backtrack(nums,track);
        return res;
    }
 
    private void backtrack(int[] nums, LinkedList track) {
        if (track.size()==nums.length){
            res.add(new LinkedList<>(track));
            return;
        }
        for (int i = 0; i 
            //排除不合法的选择 剪枝
            if (track.contains(nums[i])){
                continue;
            }
            //做选择
            track.add(nums[i]);
            //进入下一层的决策树
            backtrack(nums,track);
            //取消选择，返回上一层的树、
            track.removeLast();
        }
    }
}

 

• 只要遍历到叶子节点，这个路径就是一个排列的组合 ，这里有剪枝的操作，就是当遇到链表中出现的数字，我们就不需要往下递归了

N皇后问题

 

• 首先我们去考虑，如果不考虑列之间和斜线之间的冲突问题，那就是让我们去每一行去放一个皇后

• 如果这样去考虑，相当于第一列代表1，第二列代表2，第三列代表3， 可以选1 1 1，1 1 2，1 1 3，1 2 1.....

这种考虑的多叉树

•  走到叶子节点的路径就是我们的放置方法，我们在全部的方法中满足列和列之间不能攻击，列与列之间不能攻击的问题
• 下面就是利用不能选择的条件去剪枝

• 依靠这三个条件来判断能不能添加，进行剪枝 

class Solution {
   List> res=new LinkedList<>();//棋盘的存储
    public List> solveNQueens(int n) {
        char[][] board = new char[n][n];
        for (char[] c : board) {
            Arrays.fill(c, '.');
        }
        bakctrack(board,0);
        return res;
    }
 
    private void bakctrack(char[][] board, int row) {
        if(row==board.length){
            res.add(Array2List(board));
            return;
        }
        int n=board[0].length;
        for (int col = 0; col < n; col++) {
            //排除会发生冲突的格子
            if (!isValid(board,row,col)){
                continue;
            }
            //进行选择
            board[row][col]='Q';
            //进行下一行的放皇后
            bakctrack(board,row+1);
            //撤销选择
            board[row][col]='.';
        }
    }
    public List Array2List(char[][] chessboard) {
        List list = new ArrayList<>();
 
        for (char[] c : chessboard) {
            list.add(String.copyValueOf(c));
        }
        return list;
    }
 
    private boolean isValid(char[][] board, int row, int col) {
        int n=board.length;
        //检查列是否有冲突
        for (int i = 0; i < n; i++) {
            if (board[i][col]=='Q'){
                return false;
            }
        }
        for (int i = row-1,j=col+1; i >=0&&j
                if (board[i][j]=='Q'){
                    return false;
                }
        }
        for (int i = row-1,j=col-1; i >=0&&j>=0; i--,j--) {
             if(board[i][j]=='Q'){
                 return false;
             }
        }
        return true;
    }
}