回溯（DFS）算法解题套路框架 :: labuladong的算法小抄

[utterances-bot]

文章链接点这里：回溯（DFS）算法解题套路框架

评论礼仪 见这里，违者直接拉黑。

[tinyhare]

合法了就做选择，做下一层决策，省了一个continue语句 ，这样好不好

 for (int col = 0; col < n; col++) {
        // 选择合法位置
        if (isValid(board, row, col)) {      
            // 做选择
            board[row][col] = 'Q';
            // 进入下一行决策
            backtrack(board, row + 1);
            // 撤销选择
            board[row][col] = '.';
         }
    }

[labuladong]

@tinyhare 一样的

[Lucas-ljx]

意思是一样的

[daduizhang20240101]

请问N皇后问题，[".Q...","...Q.","Q....","....Q","..Q.."]满不满足条件

[jianli0]

合法了就做选择，做下一层决策，省了一个continue语句 ，这样好不好

continue的写法更好，guard clauses 参见这篇文章 https://betterprogramming.pub/refactoring-guard-clauses-2ceeaa1a9da

[xiangyueerli]

东哥东哥,res.add(new LinkedList(track)); 改成res.add(track);怎么就不对了呢

[labuladong]

@xiangyueerli 因为这个 track 是一个外部引用，在遍历过程中track 中的数据会不断变化，所以装入 res 的时候应该把 track 里面的值做一次拷贝。Java 可以这样用 new 实现拷贝的效果，其他语言各有自己的方式。

[coder-pig]

妙啊

[wying111]

N皇后有java版本嘛

[deepbreath373]

【Java版】不过我可能写得有点麻烦了，都是用的笨办法操作字符串😄

class Solution {
    List<List<String>> res = new ArrayList<>();
    public List<List<String>> solveNQueens(int n) {
        ArrayList<String> board = new ArrayList<>();
        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < n; i++){
            sb.append('.');
        }
        for(int i = 0; i < n; i++){
            board.add(sb.toString());
        }
        backtrack(board, 0);
        return res;
    }
    private void backtrack(ArrayList<String> board, int row){
        if(row == board.size()){
            res.add(new ArrayList<>(board));
            return;
        }
        int n = board.get(row).length();
        for(int col = 0; col < n; col++){
            if(!isValid(board, row, col)){
                continue;
            }
            String r = board.remove(row);
            StringBuilder sb = new StringBuilder(r);
            sb.replace(col, col+1, "Q");
            board.add(row, sb.toString());
            backtrack(board, row+1);
            r = board.remove(row);
            sb = new StringBuilder(r);
            sb.replace(col, col+1, ".");
            board.add(row, sb.toString());
        }
    }
    private boolean isValid(ArrayList<String> board, int row, int col){
        int n = board.size();
        for(int i = 0; i < n; i++){
            String r = board.get(i);
            if(r.charAt(col) == 'Q'){
                return false;
            }
        }
        for(int i = row - 1, j = col + 1; i >= 0 && j < n; i--,j++){
            String r = board.get(i);
            if(r.charAt(j) == 'Q'){
                return false;
            }
        }
        for(int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--){
            String r = board.get(i);
            if(r.charAt(j) == 'Q'){
                return false;
            }
        }
        return true;
    }
}

[ivemcel]

class Solution {

    List<List<String>> res = new ArrayList<>();

    /* 输入棋盘的边长n，返回所有合法的放置 */
    public List<List<String>> solveNQueens(int n) {
        // "." 表示空，"Q"表示皇后，初始化棋盘
        char[][] board = new char[n][n];
        for (char[] c : board) {
            Arrays.fill(c, '.');
        }
        backtrack(board, 0);
        return res;
    }

    public void backtrack(char[][] board, int row) {
        // 每一行都成功放置了皇后，记录结果
        if (row == board.length) {
            res.add(charToList(board));  
            return;
        }

        int n = board[row].length;
        // 在当前行的每一列都可能放置皇后
        for (int col = 0; col < n; col++) {
            // 排除可以相互攻击的格子
            if (!isValid(board, row, col)) {
                continue;
            }
            // 做选择
            board[row][col] = 'Q';
            // 进入下一行放皇后
            backtrack(board, row + 1);
            // 撤销选择
            board[row][col] = '.';
        }
    }

    /* 判断是否可以在 board[row][col] 放置皇后 */
    public 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 < n; i--, 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;
    }

    public List charToList(char[][] board) {
        List<String> list = new ArrayList<>();

        for (char[] c : board) {
            list.add(String.copyValueOf(c));
        }
        return list;
    }

}

[jswxwxf]

js 版本，利用闭包，省去了很多中间变量。

/* 输入棋盘边长 n，返回所有合法的放置 */
function solveNQueens(n) {
  // '.' 表示空，'Q' 表示皇后，初始化空棋盘。
  const board = new Array(n).fill(0).map(() => new Array(n).fill("."));
  const res = [];
  backtrack(0);
  return res;

  function isValid(row, col) {
    // 检查列是否有皇后互相冲突
    for (let i = 0; i < n; i++) {
      if (board[i][col] === "Q") return false;
    }
    // 检查右上方是否有皇后互相冲突
    for (let i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
      if (board[i][j] === "Q") return false;
    }
    // 检查左上方是否有皇后互相冲突
    for (let i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
      if (board[i][j] === "Q") return false;
    }
    return true;
  }

  // 路径：board 中小于 row 的那些行都已经成功放置了皇后
  // 选择列表：第 row 行的所有列都是放置皇后的选择
  // 结束条件：row 超过 board 的最后一行
  function backtrack(row) {
    // 触发结束条件;
    if (row === board.length) {
      res.push(board.map((row) => row.join("")));
      return;
    }

    for (let col = 0; col < n; col++) {
      // 排除不合法选择;
      if (!isValid(row, col)) {
        continue;
      }
      // 做选择;
      board[row][col] = "Q";
      // 进入下一行决策;
      backtrack(row + 1);
      // 撤销选择;
      board[row][col] = ".";
    }
  }
}

console.log(solveNQueens(4));

[xqhgit]

Python3版本

class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        result = []
        board = []
        for i in range(n):
            board.append(['.'] * n)

        def isValid(row, col):
            # 检查列是否有皇后
            for i in range(n):
                if board[i][col] == 'Q':
                    return False

            # 检查右上方是否有皇后
            i = row - 1
            j = col + 1
            while i >= 0 and j < n:
                if board[i][j] == 'Q':
                    return False
                i -= 1
                j += 1

            # 检查左上方是否有皇后
            i = row - 1
            j = col - 1
            while i >= 0 and j >= 0:
                if board[i][j] == 'Q':
                    return False
                i -= 1
                j -= 1

            return True

        def backtrack(row):
            # 超出左后一行
            if row == n:
                result.append([''.join(b) for b in board])
                return

            for col in range(n):
                # 排除不合法选择
                if not isValid(row, col):
                    continue
                # 做选择
                board[row][col] = 'Q'
                # 进入下一秒决策
                backtrack(row + 1)
                # 撤销选择
                board[row][col] = '.'

        backtrack(0)
        return result

[huoshaninmountain]

左右斜和竖线都可以用数组记录是否已被占据，代码更简洁高效

class Solution {
public:
    vector<vector<string>> res;
    vector<vector<string>> solveNQueens(int n) {
        /*左斜编号由board[n-1][0]->l[0]，往右上依次记录每条斜线,右斜由[0][0]->[0]往下*/
        vector<bool> colflag(n,false),ldiag(2*n-1,false),rdiag(2*n-1,false);
        vector<string> board(n,string(n,'.'));
        backtrack(board,n,0,colflag,ldiag,rdiag);
        return res;
    }
    void backtrack(vector<string>& board,int n,int row,vector<bool>& colflag,vector<bool>&ldiag,vector<bool>&rdiag){
        if(row==n){res.push_back(board);return;}
        for(int col=0;col<n;col++){
            if(colflag[col]||ldiag[n-1-row+col]||rdiag[row+col])continue;

            board[row][col]='Q';
            colflag[col]=ldiag[n-1-row+col]=rdiag[row+col]=true;
            backtrack(board,n,row+1,colflag,ldiag,rdiag);
            board[row][col]='.';
            colflag[col]=ldiag[n-1-row+col]=rdiag[row+col]=false;
        }
    }
};

[Leloz00]

东哥YYDS！

[zhongweiLeex]

package leetcode.backtrack;

import java.util.LinkedList;
import java.util.List;

public class SolveNQueens51 {

    List<List<String>> result = new LinkedList<>();//存放所有结果

    public List<List<String>> solveNQueens(int n) {
        //新建一个棋盘
        List<String> board = new LinkedList<>();
        StringBuilder stringBuilder = new StringBuilder();
        //初始化棋盘 全部置空
        stringBuilder.append(".".repeat(n));
        for (int i = 0; i < n; i++) {
            board.add(stringBuilder.toString());
        }
        backTrack(0,board);
        return result;

    }
    /**
     * @param board 棋盘情况
     * @param row 当前游标处于第几行
     * */
    private void backTrack(int row,List<String> board){
        //回溯终止条件
        if (row == board.size()){//终止条件 递归到了最后一个行 直接跳出
            result.add(new LinkedList<>(board));//将目前的结果中的添加到result中
            return;
        }
        int n = board.get(row).length();//获取当前游标所在的行的 String长度
        //开始穷举 从 当前行的 第0 列开始 处理节点
        for (int col = 0; col < n ; col++) {
            //处理节点 （检查节点合法性 ， 如果合法 ）
            if (!isValid(row,col,board)){//检查 当前行 的 所有列的节点是否合法
                continue;//如果不合法直接跳过
            }
            String str = board.get(row).substring(0,col) + 'Q' + board.get(row).substring(col+1);

            board.set(row,str);//将上述的替换后的String 代替到 游标所在的row

            //递归 深入子树
            backTrack(row+1,board);//对深入的下一行进行递归操作

            //回溯 ，撤销处理结果
            str = board.get(row).substring(0,col) + '.' + board.get(row).substring(col+1);
            board.set(row,str);
        }
    }
    /**
     * @param row  // 检查游标 目前 所有在的行位置
     * @param column //检查游标 目前的 所在的列位置
     * @param board //当前的棋盘状态
     * @apiNote 判断是否当前位置是否合法
     * */
    private boolean isValid(int row,int column,List<String> board){
        int n = board.size();
        //判断列位置是否合法
        for (int i = 0; i < n; i++) {
            if (board.get(i).charAt(column) == 'Q'){//第 i行 第 column 列 的字符
                return false;
            }
        }
        //判断是否与右上方发生冲突
        for (int i = row -1,j = column + 1; i >= 0 && j < n; i--,j++ ) {
            if (board.get(i).charAt(j) == 'Q'){
                return false;
            }
        }
        //判断 是否与 左上方冲突
        for (int i = row -1,j = column -1 ; i >=0 && j>=0 ; i--,j--) {
            if (board.get(i).charAt(j) == 'Q'){
                return false;
            }
        }
        return true;
    }
}

[wangnan0916]

同列判断用y记录，斜线判断xdy，xay PS：开200 是为了防止出现负数下标

class Solution {
public:
    vector<vector<string>> solveNQueens(int n) {
        typedef vector<string> vs;
        vector<vs>ans;
        vs path(n,string(n,'.'));
        bool y[10]={0},xdy[200]={0},xay[200]={0};
        function<void(int)>backtrack=[&](int row){
            if(row==n){
                ans.push_back(path);
                return ;
            }
            for(int i=0;i<n;i++){
                if(xdy[row-i+100]||xay[row+i]||y[i])continue;
                path[row][i]='Q';
                xdy[row-i+100]=1,xay[row+i]=1,y[i]=1;
                backtrack(row+1);
                xdy[row-i+100]=0,xay[row+i]=0,y[i]=0;
                path[row][i]='.';
            }
        };
        backtrack(0);
        return ans;
    }
};

[wy471x]

貌似，正下方和正上方都做了检查，文章说的正下方不用做检查这句是不是有点问题？

[zzjzzy]

java版，用二维char数组来表示棋盘

class Solution {
    List<List<String>> result = new ArrayList<>();
    char[][] board = null;

    public List<List<String>> solveNQueens(int n) {
        board = new char[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                board[i][j] = '.';
            }
        }
        solve(n, 0);
        return result;
    }

    private void solve(int n, int rowNum) {
        if (rowNum == n) {
            List<String> boardResult = new ArrayList<>(n);
            for (char[] row : board) {
                boardResult.add(new String(row));
            }
            result.add(boardResult);
            return;
        }

        for (int col = 0; col < n; col++) {
            if (isValid(rowNum, col, n)) {
                board[rowNum][col] = 'Q';
                solve(n, rowNum + 1);
                board[rowNum][col] = '.';
            }
        }
    }

    private boolean isValid(int rowNum, int col, int n) {
        // 检查行
        for (int i = 0; i < rowNum; i++) {
            if (board[i][col] == 'Q') {
                return false;
            }
        }

        // 检查列
        for (int i = 0; i < n; i++) {
            if (i != col && board[rowNum][i] == 'Q') {
                return false;
            }
        }

        // 检查左上
        int i = rowNum - 1;
        int j = col - 1;
        while (i >= 0 && j >= 0) {
            if (board[i][j] == 'Q') {
                return false;
            }
            i--;
            j--;
        }

        // 检查右上
        i = rowNum - 1;
        j = col + 1;
        while (i >= 0 && j < n) {
            if (board[i][j] == 'Q') {
                return false;
            }
            i--;
            j++;
        }

        return true;
    }
}

[zizxzy]

全排列js版本

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var res = [];
var permute = function (nums) {
    const backtrack = (nums, track, used) => {
        if (nums.length === track.length) {
            res.push(track.slice());
            return;
        }
        const length = nums.length;
        for (let i = 0; i < length; i++) {
            if (used[i]) {
                continue;
            }
            track.push(nums[i]);
            used[i] = true;
            backtrack(nums, track, used);
            used[i] = false;
            track.pop();
        }
    };
    const track = [],
        used = new Array(nums.length);
    backtrack(nums, track, used);
    return res;

};

[1181406961]

从第一章二叉树那里过来的，现在才搞明白其实回溯不就是后续遍历嘛。之前做八皇后想破头都搞不出来，现在10分钟搞定。不得不说东哥yyds!!!。

[labuladong]

@1181406961 应该说回溯是前序做选择，后序撤销选择。但更准确点说，这个前序和后序的位置是排除了根节点的，这里 讨论了回溯算法和标准多叉树的区别。

[TimurJiangShan]

N皇后，还是有点不清楚最后的“撤销”的操作的语义是什么，有点懵懵的，为啥要撤销呢

[labuladong]

@TimurJiangShan 回溯算法就是单纯的穷举所有可能性，然后从所有可能的结果中选择出真正满足条件的结果。那么每找到一个结果后，需要把之前做的选择撤销掉，然后才能去寻找新的结果。

[LovesAsuna]

东哥能不能教教怎么用回溯打印所有的出栈序列？我在复习验证栈序列那题的时候突发奇想想换种方法用回溯来做这题，但是下手的时候就不会写了

[oyb001]

// 提交一份 Golang的写法
func solveNQueens(n int) [][]string {
    return NBoard(n)
}

func Board(n int, str string) [][]string {
    res := make([][]string, n)
    for i, _ := range res {
        // 第二维数组数据填
        v2 := make([]string, n)
        for j, _ := range v2 {
            v2[j] = str
        }
        res[i] = v2
    }
    return res
}

func NBoard(n int) [][]string {
    res := make([][]string, 0, n)
    // 结果集初始化
    for i, _ :=range res {
        res[i] = make([]string, 0, n)
    }

    var dfs func(board [][]string, row int)
    dfs = func(board [][]string, row int) {
        // 结束条件,row的长度等于board长度
        if row == len(board) {
            // 复制这个数组
            res1 := make([]string,0, n)
            for i := 0 ;i <n ; i++ {
                //RowTemp := make([]string, n)
                //copy(RowTemp, board[i])
                res1 = append(res1, strings.Join(board[i], ""))
            }
            res = append(res, res1)
            return
        }

        // 获取当前棋盘的列数量
        n := len(board[row])
        // 对该列进行遍历
        for col := 0 ; col < n ; col++ {
            // 排除不合法的选择
            if !IsVaild(board, row, col) {
                continue
            }
            // 做选择
            board[row][col] = "Q"
            // 进行下一项决策
            dfs(board, row+1)
            // 撤销选择
            board[row][col] = "."
        }
    }
    board := Board(n, ".")
    dfs(board, 0)
    return res
}

// 判断当前位置是否可以放置皇后
func IsVaild(board [][]string, row ,col int) bool {
    // 获取棋盘的宽度
    n := len(board)
    // 检查该列是否有皇后冲突
    for i :=0 ; i < n; i ++ {
        if board[i][col] == "Q" {
            return false
        }
    }

    // 检查左上角是否有冲突，遍历条件行减列减
    i := row - 1
    j := col -1
    for i >= 0 && j >= 0 {
        if board[i][j] == "Q" {
            return false
        }
        i--
        j--
    }
    // 检查右上角是否有冲突，遍历条件行减列加
    i1 := row -1
    j1 := col + 1
    for i1 >= 0 && j1 < n {
        if board[i1][j1] == "Q" {
            return false
        }
        i1--
        j1++
    }
    return true
}

[billgoo]

2022.3.29 mark

[zhongweiLeex]

请问什么时候用List 什么时候用LinkedList？ 这儿两个data structure有什么优劣吗

关于这个问题，建议先去好好复习一下java，这里简单讲述一下： 一个是抽象接口，一个是具体实现类，这里是体现了多态而已，建议回去好好再复习一下java容器相关。

[7Vivi7]

N皇后 ==Java版本== 感谢东哥

class Solution {

    List<List<String>> res = new LinkedList<>();

    public List<List<String>> solveNQueens(int n) {
        List<StringBuffer> board = new ArrayList<>();
        StringBuffer sb = new StringBuffer();
        for (int i = 0; i < n; i++) {
            sb.append(".");
        }
        // 初始化空棋盘
        for (int i = 0; i < n; i++) {
            board.add(new StringBuffer(sb.toString()));
        }
        backtrack(board, 0);
        return res;
    }

    void backtrack(List<StringBuffer> board, int row) { 

        int n = board.size();
        if (n == row) {
            List<String> t = new ArrayList<>();
            for (StringBuffer s : board) {
                t.add(s.toString());
            }
            res.add(t);
            return;
        }

        int x = board.size();
        for (int col = 0; col < x; col++) {
            if (!isVaild(board, row, col)) {
                // 不合法的选择
                continue;
            }

           board.get(row).replace(col, col + 1, "Q");
           backtrack(board, row + 1);
           board.get(row).replace(col, col + 1, ".");
        }
    }

    // 是否可以在 row col 放置皇后
    boolean isVaild(List<StringBuffer> board, int row, int col) {
        int n = board.size();

        // 检查列
        for (int i = 0; i < n; i++) {
            if (board.get(i).charAt(col) == 'Q') {
                return false;
            }
        }

        // 检查右上方
        for (int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
            if (board.get(i).charAt(j) == 'Q') {
                return false;
            }
        }
        // 检查左上方
        for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
            if (board.get(i).charAt(j) == 'Q') {
                return false;
            }
        }
        return true;
    }
}

[PandyYang]

@yiiiq 接口实现类都没玩明白，你应该先把基础再好好看一下。

[baoyun-chen]

class Solution {

   public List<List<String>> result = new ArrayList<List<String>>();
    public List<List<String>> solveNQueens(int n) {
        List<Integer> position = new ArrayList<>(n);
        List<String> way = new ArrayList<>();
        int index = 0;
        while(index < n){
            position.add(index);
            index++;
        }
        placeQueen(position, way,n, -2);
        return result;
    }

    public void placeQueen(List<Integer> position, List<String> way, int queueNum, int lastRowPosition){
        if(way.size() == queueNum){
            List<String> addWay = new ArrayList<>(way);
            result.add(addWay);
            return;
        }

        for(int index = 0; index < position.size(); index++){
            Integer element = position.get(index);
            if(element <= lastRowPosition + 1 && element >= lastRowPosition - 1){
                continue;
            }

            String row = buildString(queueNum, element);
            way.add(row);
            position.remove(index);

            placeQueen(position,way,queueNum,element);

            position.add(index, element);
            way.remove(way.size()-1);

        }

    }

    private String buildString(int n, int position){
        StringBuilder builder = new StringBuilder();
        int index = 0;
        while(index < n){
            char addChar = '.';
            if(index == position){
                addChar = 'Q';
            }
            builder.append(addChar);
            index++;
        }

        return builder.toString();
    }
}

请教各位，为什么这样的算法算出来会多了 N=5 的时候 其中一个多出来的例子是 [".Q...","...Q.","Q....","....Q","..Q.."]

这种情况为什么不行？

[dreamer2q]

写模式，优化检查合法落子逻辑

手动维护一个棋盘，初始值都是 0，当有 Q 落子时候，将以 Q 为中心的位置，从上到下，从左到右，两个斜对角的棋盘值更新为原来值+1。比如说一开始是 0，然后更新完成之后 Q 能吃子的地方都设置成了 1。

撤销落子 Q 时候，执行相反的操作，即 Q 影响的棋盘位置更新为原来值-1。

这样只需要判断棋盘某一个位置值是否为 0，就能找到 Q 落子是否合法了。好处就是，回溯搜索大部分都在寻找一个合法的落子位置，通过此方式可以优化寻找合法落子的时间。

/**
 * @param {number} n
 * @return {string[][]}
 */
var solveNQueens = function (n) {
  qb = new Array();
  for (let i = 0; i < n; i++) {
    qb.push(new Array(n).fill(0));
  }

  ans = [];
  path = [];
  traverse(n, 0);
  return ans;
};

let qb = [];
let ans = [];
let path = [];

function traverse(n, row) {
  if (row === n) {
    //找到解了, 输出一个解法
    ans.push([...path]);
    return;
  }

  for (let i = 0; i < n; i++) {
    if (canIput(row, i)) {
      let line = putQueue(row, i);
      path.push(line);
      traverse(n, row + 1);
      unputQueue(row, i);
      path.pop();
    }
  }
}

function canIput(row, x) {
  return qb[row][x] === 0;
}

function putQueue(row, x) {
  updateQueue(row, x, (v) => v + 1);
  let line = new Array(qb.length).fill(".");
  line[x] = "Q";
  return line.join("");
}

function unputQueue(row, x) {
  return updateQueue(row, x, (v) => v - 1);
}

function updateQueue(row, x, update) {
  let n = qb.length;
  for (let i = 0; i < n; i++) {
    qb[row][i] = update(qb[row][i]);
    qb[i][x] = update(qb[i][x]);
    let r = row - x + i;
    if (r >= 0 && r < n) {
      qb[r][i] = update(qb[r][i]);
    }
    let r2 = row + x - i;
    if (r2 >= 0 && r2 < n) {
      qb[r2][i] = update(qb[r2][i]);
    }
  }
}

[saw008]

@baoyun-chen
你的棋盘第3行和第5行是相互不满足的。

[1302304703]

最还原东哥的N皇后版本，一模一样的回溯思路（java）

public class Solution51 {

    public List<String> track;

    public List<List<String>> res = new LinkedList<>();

    public List<List<String>> solveNQueens(int n) {
        track = new LinkedList<>();
        char[][] board = new char[n][n];
        for (int i = 0; i < n; i++) {
            Arrays.fill(board[i], '.');
        }
        backtrack(board, 0);
        return res;
    }

    public void backtrack(char[][] board, int row) {
        if (track.size() == board.length) {
            res.add(new LinkedList<>(track));
            return;
        }

        for (int i = 0; i < board.length; i++) {
            if (!isValid(board, row, i)) {
                continue;
            }
            board[row][i] = 'Q';
            track.add(new String(board[row]));

            backtrack(board, row + 1);

            board[row][i] = '.';
            track.remove(track.size() - 1);
        }
    }

    public 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 < n; i--, 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;
    }
}

[jrr997]

Valid方法中检查列是否有皇后互相冲突的循环条件为什么不是

for (int i = 0; i <= row; i++)

文章也说了只用检查上面，左上，右上三个方向，i < n应该检查了下方了吧

[yangyj1994]

xiangyueerli commented on 2021年12月9日 东哥东哥,res.add(new LinkedList(track)); 改成res.add(track);怎么就不对了呢

[saw008]

xiangyueerli commented on 2021年12月9日 东哥东哥,res.add(new LinkedList(track)); 改成res.add(track);怎么就不对了呢

你应当复制track到一个新的对象，否则你一直引用的是同一个track，然后到后来track在被修改时，你存储在res的track也同时被修改了

[labuladong]

@jrr997 嗯，可以的。文中代码有点瑕疵，已修改

[zhongweiLeex]

回溯法 高频率题：

1. 字符串排列 解法

   class Solution {
   private HashSet<String> result = new HashSet<>();
   private boolean[] visited;
   
   public String[] permutation(String s) {
   
       char[] ch = s.toCharArray();
       visited = new boolean[s.length()];//记录此字符是否被访问过
   
       backTrace(ch,0,new StringBuilder());
   
       String[] str = result.toArray(new String[0]);//使用set去重，如果不适用set，其他方法可能超时 此处可以优化
       return result.toArray(new String[0]);
   }
   private void backTrace(char[] ch,int index,StringBuilder list){
   
       if(index == ch.length){
           result.add(list.toString());
       }
   
       for(int i = 0; i< ch.length ; i++){
   
           if(visited[i] == true) continue;
   
           //做选择
           list.append(ch[i]);
           visited[i] = true;
   
           backTrace(ch,index+1,list);
   
           //撤销选择
           list.deleteCharAt(list.length() -1);
           visited[i] = false;
       }
   }
   }

2. 复原IP地址

   class Solution {
   List<String> result = new LinkedList<>();
   public List<String> restoreIpAddresses(String s) {
   
       if(s.length() > 12){//不符合要求 返回空的result
           return result;
       }
       backTrace(s,0,0);
       return result;
   
   }
   private void backTrace(String str,int index,int pointSum){
   
       if(pointSum == 3){
           //检查第三个点后面的数字是否合法
           if(isValid(str,index,str.length()-1)){
               result.add(str);
           }
           return;
       }
   
       for(int i = index; i< str.length(); i++){
   
           if(!isValid(str,index,i)){
               break;
           }
   
           //回溯做选择
           str = str.substring(0,i+1) + "." + str.substring(i+1);
           pointSum++;
   
           backTrace(str,i+2,pointSum);
   
           //撤销选择
           pointSum--;
           str = str.substring(0,i+1) + str.substring(i+2);
       }
   }
   //检查合法性
   private boolean isValid(String str,int start , int end){
       if(start> end){
           return false;
       }
       //0开头不合法
       if(str.charAt(start) == '0' && start!= end){
           return false;
       }
       int num=0;
       //检查start 到 end是否合法
       for(int i = start; i <=end;i++){
   
           if(str.charAt(i) < '0' || str.charAt(i)>'9'){
               return false;
           }
           num = num*10 + (str.charAt(i)-'0');
           if(num > 255){
               return false;
           }
       }
       return true;
   }
   }

3. 分割回文串

   class Solution {
   private List<List<String>> result = new LinkedList<>();
   public List<List<String>> partition(String s) {
   
       backTrack(s,0,new LinkedList<String>());
       return result;
   }
   
   private void backTrack(String s, int startIndex,LinkedList<String> list){
       if(startIndex == s.length()){
           result.add(new LinkedList<>(list));
           return;
       }
   
       for(int i = startIndex; i< s.length(); i++ ){
           String sub = s.substring(startIndex,i+1);
           int subLength = sub.length();
           if(!isValid(sub)){
               continue;
           }
   
           list.add(sub);
           backTrack(s,startIndex+subLength,list);//注意此处需要添加的 subLength 不是 简单 +1 //自己想原因哈哈哈哈
           list.removeLast();
       }
   }
   
   //判断字符串是否是回文字符串
   private boolean isValid(String s){
       if(s == null || s.length() <=1){
           return true;
       }
       int i = 0;
       int j = s.length()-1;
       while(i<j){
           if(s.charAt(i) != s.charAt(j)){
               return false;
           }
           i++;
           j--;
       }
       return true;
   }
   }

[lyStray]

请问最差时间复杂度为啥不是O(N^N)，而是O(N^(N+1))

[labuladong]

@strayLuoY 可以化简，都是对的

[chenye-814]

@strayLuoY 因为递归和遍历的地方是N^N, 然后每次validate是N的时间复杂度，所以总共就是N^（N+1）。 用三个hashset之类的东西存储之前的col，row+col，row-col的值，应该可以实现N^N。

import java.util.*;

class Solution {

    private List<List<String>> res = new LinkedList<>();

    private Set<Integer> colSet = new HashSet<>();
    private Set<Integer> rowPlusColSet = new HashSet<>();
    private Set<Integer> rowMinusColSet = new HashSet<>();

    public List<List<String>> solveNQueens(int n) {
        if (n == 1)
            res.add(List.of("Q"));
        else if (n == 2)
            return res;
        else {
            char[][] board = new char[n][n];
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++)
                    board[i][j] = '.';
            }
            solve(board, 0, n);
        }
        return res;
    }

    private void solve(char[][] board, int row, int n) {
        if (row == n) {
            List<String> ans = new ArrayList<>(n);
            for (char[] charSeq : board)
                ans.add(String.valueOf(charSeq));
            res.add(ans);
        } else {
            for (int col = 0; col < n; col++) {
                if ( !colSet.contains(col) 
                    && !rowPlusColSet.contains(row + col)
                    && !rowMinusColSet.contains(row - col)) {
                        colSet.add(col);
                        rowPlusColSet.add(row+col);
                        rowMinusColSet.add(row-col);
                        board[row][col] = 'Q';
                        solve(board, row+1, n);
                        board[row][col] = '.';
                        colSet.remove(col);
                        rowPlusColSet.remove(row+col);
                        rowMinusColSet.remove(row-col);
                }
            }
        }
    }

}

[bert82503]

打卡，感谢！

[bert82503]

Java版，使用char二维数组表示棋盘。

class Solution {
    // 输入棋盘边长 n，返回所有合法的放置
    public List<List<String>> solveNQueens(int n) {
        // 1、路径，记录你已经做过的选择
        // '.'表示空，'Q'表示皇后，初始化空棋盘
        char[][] board = new char[n][n];
        for (char[] row : board) {
            Arrays.fill(row, '.');
        }
        backtrack(board, 0);
        return res;
    }

    // 记录结果
    List<List<String>> res = new LinkedList<>();

    // 路径：board 中小于 row 的那些行都已经成功放置了皇后
    // 选择列表：第 row 行的所有列都是放置皇后的选择
    // 结束条件：row 超过 board 的最后一行
    void backtrack(char[][] board, int row) {
        // 3、结束条件，就是遍历到树的底层叶子节点，这里也就是选择列表为空的时候
        if (row == board.length) {
            res.add(applyAsList(board));
            return;
        }

        // 2、选择列表，表示你当前可以做出的选择
        int n = board[0].length;
        for (int col = 0; col < n; col++) {
            // 前序位置
            // 排除不合法的选择
            if (!isValid(board, row, col)) {
                continue;
            }
            // 做选择
            board[row][col] = 'Q';
            // 进入下一行决策
            backtrack(board, row + 1);
            // 后序位置
            // 撤销选择/取消选择
            board[row][col] = '.';
        }
    }

    // 是否可以在 board[row][col] 放置皇后？
    boolean isValid(char[][] board, int row, int col) {
        int n = board.length;
        // 检查列是否有皇后互相冲突
        for (int i = 0; i < row; i++) {
            if (board[i][col] == 'Q') {
                return false;
            }
        }
        // 检查右上方是否有皇后互相冲突
        for (int i = row - 1, j = col + 1; i >= 0 && j < n; i--, 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;
    }

    List<String> applyAsList(char[][] board) {
        List<String> ans = new ArrayList<>(board.length);
        for (char[] row : board) {
            ans.add(new String(row));
        }
        return ans;
    }
}

[massiachan]

在处理【排除不合法的选择】这一步时，到底是在本层循环排出更好呢，还是在进入下一层循环前判断比较好？ 在做77题的时候，我看LC上很多答案会把排除不合法放在回溯语句的第二行，即超boundary 就return false，这样运行出来会更快呢，是为什么呢？

[bert82503]

@massiachan 看【排除不合法的选择】判断成本是多少？ “把排除不合法放在回溯语句的第二行”的前提是结束条件返回的结果是正确的。 在本层循环排除更好，不会递归进入下一行决策回溯树/决策树剪枝更多。 在进入下一层循环前判断，多了一次递归调用。

[LebronHarden1]

java版本

class Solution {
    List<List<String>> res = new LinkedList<>();
    public List<List<String>> solveNQueens(int n) {
        //n皇后问题,本质还是回溯,即穷举
        //利用二维数组做棋盘
        char[][] board = new char[n][n];
        //对棋盘进行初始化,没落子的地方都是'.'
        for(char[] arr:board){
            Arrays.fill(arr,'.');
        }
        //因为要维护路径和选择列表,路径就是小于row的那些行所放置的皇后位置情况
        //选择列表就是第row行的所有列都有可能被选择
        //结束条件就是row超过board的最后一行
        backTrack(board,0);
        return res;
    }
    private void backTrack(char[][] board,int row){
        //结束条件
        if(row==board.length){
            res.add(helper(board));//helper作用就是把二维字符数组处理成测试用例那样的形式
            return;
        }
        //穷举
        for(int col=0;col<board.length;col++){
            if(!isValid(board,row,col)) continue;
            //做选择
            board[row][col]='Q';
            //回溯
            backTrack(board,row+1);
            //撤销选择
            board[row][col]='.';
        }
    }
    private boolean isValid(char[][] board,int row,int col){
        //因为是一行一行从上往下放的,所以我们只需要检查会不会和:左上,正上,右上三个方向的某个皇后打架就ok
        //左上
        for(int i=row-1, j=col-1;i>=0&&j>=0;i--,j--){
            if(board[i][j]=='Q') return false;
        }
        //正上方
        for(int i=row-1;i>=0;i--){
            if(board[i][col]=='Q') return false;
        }
        //右上
        for(int i=row-1,j=col+1;i>=0&&j<board.length;i--,j++){
            if(board[i][j]=='Q') return false;
        }
        return true;
    }
    private List<String> helper(char[][] board){
        List<String> list = new ArrayList<>();
        for(char[] arr:board){
            list.add(String.copyValueOf(arr));
        }
        return list;
    }
}

[EricESM]

差不多思路

class Solution {
    int n;
    int[] rows;
    boolean[] col;
    boolean[] dl;
    boolean[] dr;
    List<List<String>> result = new ArrayList<>();

    public List<List<String>> solveNQueens(int n) {
        this.n = n;
        rows = new int[n];
        col = new boolean[n];
        dl = new boolean[2*n-1];
        dr = new boolean[2*n-1];

        search(0);
        return result;
    }

    void search(int a) {
        if (a >= n) {
            List<String> board = getBoard();
            result.add(board);
        } else {
            for (int i=0;i<n;i++) {
                if (!col[i] && !dl[i + a] && !dr[n-1-i + a]) {
                    col[i] = true;
                    dl[i+a] = true;
                    dr[n-1-i+a] = true;
                    rows[a] = i;
                    search(a+1);
                    col[i] = false;
                    dl[i+a] = false;
                    dr[n-1-i+a] = false;
                }
            }
        }
    }

    List<String> getBoard() {
        List<String> rs = new ArrayList<>();
        char[] cs = new char[n];
        for (int i=0;i<n;i++) {
            Arrays.fill(cs, '.');
            cs[rows[i]] = 'Q';
            rs.add(new String(cs));
        }
        return rs;
    }
}

[saw008]

我有一个问题，对于八皇后问题，为什么整体复杂度不是O(N!N)呢？valid函数的复杂度是O(N)，而主函数本身的复杂度是O(N!)，因为我们在搜索可能的放置棋子的位置时，先判断了是否valid，是就递归；否则跳过，而每次的选择空间从第一行到最后一行，是由N到1递减的，所以可行方案只有N!种。整体的复杂度就是相乘，得出O(N!N)了。

[labuladong]

@saw008 你说的有道理。我这里给出的复杂度估计非常粗略，完全不考虑皇后之间互相攻击的情况，虽然按照 算法时空复杂度分析实用指南 中所说，我的这个复杂度作为上界也不算错，但显然你给出的上界更紧一些，所以你的复杂度更好。我在文中修改一下，感谢指出。