回溯（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] = '.';
         }
    }

[mengfanxiao777]

没啥区别

[yimuu]

有啥区别

[l-qiang]

这种写法习惯会容易造成if层数嵌套太多

[xiaozengbing]

不好，代码尽量避免嵌套结构

[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);怎么就不对了呢

[feng0909]

为什么这里是new LinkedList(track)，是因为后面取消选择的时候会removeLast，最终会把当前track元素都移除掉，导致最后添加进去的数组都是空的

[labuladong]

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

[Peter88645]

写python得时候 就是因为忘记 深拷贝一下，导致debug了很久

[coder-pig]

妙啊

[wying111]

N皇后有java版本嘛

[ran675]

flip是异或, 第一次写入, 第二次擦除. 看力扣解数独的解法改的.
可以把 坐标 i, j 共线关系, 看成 是线性规划中 x-y+n=0, 这种线, 位置是相对的, 因此 n 是多少不重要, 只要2n - x -y >0, 不是负数下标.
凡是元素不能共线, 元素坐标有函数关系的, 都能优化成位运算

    class Solution {
        List<List<String>> res;
        char[] ch;
        int slash;
        int div;
        int vertical;

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

        void backtrack(LinkedList<String> board, int n, int i) {
            if (n == i) {
                res.add(new ArrayList<>(board));
                return;
            }
            char[] clone = ch.clone();
            int a, b, c;
            for (int j = 0; j < n; j++) {
                if ((vertical & (a = 1 << j)) != 0 ||
                        (slash & (b = 1 << i - j + n)) != 0 ||
                        (div & (c = 1 << (n << 1) - i - j)) != 0) {
                    continue;
                }
                clone[j] = 'Q';
                board.add(new String(clone));
                flip(a, b, c);
                backtrack(board, n, i + 1);
                board.removeLast();
                flip(a, b, c);
                clone[j] = '.';
            }
        }

        void flip(int a, int b, int c) {
            vertical ^= a;
            slash ^= b;
            div ^= c;
        }
    }

[ran675]

    class Solution {
        List<List<String>> res;
        char[] ch;
        int slash;
        int div;
        int vertical;
        String[] stack;
        int top;

        public List<List<String>> solveNQueens(int n) {
            res = new ArrayList<>();
            ch = new char[n];
            stack = new String[n];
            Arrays.fill(ch, '.');
            backtrack(n, 0);
            return res;
        }

        void backtrack(int n, int i) {
            if (n == i) {
                String[] clone = stack.clone();
                res.add(Arrays.asList(clone));
                return;
            }
            char[] clone = ch.clone();
            int a, b, c, digit;
            for (int mask = ~vertical & (1 << n) - 1; mask != 0; mask ^= digit) {
                digit = mask & (-mask);
                int j = Integer.bitCount(digit - 1);
                if ((vertical & (a = 1 << j)) != 0 ||
                        (slash & (b = 1 << i - j + n)) != 0 ||
                        (div & (c = 1 << (n << 1) - i - j)) != 0) {
                    continue;
                }
                clone[j] = 'Q';
                stack[top++] = new String(clone);
                flip(a, b, c);
                backtrack(n, i + 1);
                top--;
                flip(a, b, c);
                clone[j] = '.';
            }
        }

        void flip(int a, int b, int c) {
            vertical ^= a;
            slash ^= b;
            div ^= c;
        }
    }

[cetuer]

public class $51 {
    public final static List<List<String>> res = new ArrayList<>();
    public static List<List<String>> solveNQueens(int n) {
        char[][] board = new char[n][n];
        for (char[] row : board) {
            Arrays.fill(row, '.');
        }
        backtrack(board, 0);
        return res;
    }

    public static void backtrack(char[][] board, int row) {
        if(row == board.length) {
            res.add(Arrays.stream(board).map(String::valueOf).collect(Collectors.toList()));
            return;
        }
        int length = board[row].length;
        for (int i = 0; i < length; i++) {
            if(!isValid(board, row, i)) continue;
            board[row][i] = 'Q';
            backtrack(board, row + 1);
            board[row][i] = '.';
        }
    }

    public static boolean isValid(char[][] board, int row, int col) {
        // 检查列
        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 >= 0; i--, j--) {
            if(board[i][j] == '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;
    }

    public static void main(String[] args) {
        List<List<String>> lists = solveNQueens(1);
        for (List<String> list : lists) {
            for (String s : list) {
                System.out.println(s);
            }
            System.out.println("------------------");
        }

        System.out.println(lists.size());
    }
}

[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;
    }
}

[cetuer]

优雅，永不过时！

public class $51 {
    public final static List<List<String>> res = new ArrayList<>();
    public static List<List<String>> solveNQueens(int n) {
        char[][] board = new char[n][n];
        for (char[] row : board) {
            Arrays.fill(row, '.');
        }
        backtrack(board, 0);
        return res;
    }

    public static void backtrack(char[][] board, int row) {
        if(row == board.length) {
            res.add(Arrays.stream(board).map(String::valueOf).collect(Collectors.toList()));
            return;
        }
        int length = board[row].length;
        for (int i = 0; i < length; i++) {
            if(!isValid(board, row, i)) continue;
            board[row][i] = 'Q';
            backtrack(board, row + 1);
            board[row][i] = '.';
        }
    }

    public static boolean isValid(char[][] board, int row, int col) {
        // 检查列
        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 >= 0; i--, j--) {
            if(board[i][j] == '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;
    }

    public static void main(String[] args) {
        List<List<String>> lists = solveNQueens(1);
        for (List<String> list : lists) {
            for (String s : list) {
                System.out.println(s);
            }
            System.out.println("------------------");
        }

        System.out.println(lists.size());
    }
}

[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！

[NOS-AE]

感谢大佬的backtrack框架！

[CarlLy7]

二刷打卡

[abc7531265]

打卡 看得太舒服了

[Y80]

isValid(row, col) 用来验证：是否可以在 board[row][col] 放置皇后？
具体来说，如果 board[row][col] = 'Q'，要求以该点为中心，正上方所有点、左上方所有点、右上方所有点，都必须不能有 Q。
所以我觉得验证列上是否合法的 for 循环，写成下面这样更好（这样也和另外两个 for 更对仗）：

   for (int i = row - 1; i >= 0; i--) {
        if (board[i][col] == 'Q')
            return false;
    }

[forexgg]

可以这样写，就一致了。并且更简洁些。

            # check the diagonal (top left to bottom right)
            for i, j in zip(range(row), range(col)):
                if board[i][j] == 'Q':
                    return False 

好像本页面使用的 giscus，没有修改自己评论的功能？

[forexgg]

My bad。上面的代码还是应该写成（倒着查）：
因为，zip的函数，是从两个list里，按照最短的来zip。正序zip，当row > col 的时候会有问题。

    # check the diagonal (top left to bottom right)
    for i, j in zip(range(row-1, -1, -1), range(col-1, -1, -1)):
        if board[i][j] == 'Q':
            return False

[forexgg]

在检查 column 是否有冲突的时候，应该不需要 loop 到 row，到 row-1 就够了

            # check the column
            for i in range(row):
                if board[i][col] == 'Q':
                    return False

[ping2h]

回溯算法是在遍历「树枝」，DFS 算法是在遍历「节点」，总结的太好了

[wen-shuai]

牛逼，赞了

[willzhengwang]

可视化动画太赞了！

[JeanYang2]

52、N皇后II Python版本打卡

class Solution:
    def totalNQueens(self, n: int) -> int:
        self.res=0
        temp=[['.']*n for _ in range(n)]
        self.backtrack(n,0,temp)
        return self.res
    
    def backtrack(self,n,row,temp):
        #结束条件
        if row==n:
            self.res+=1

        for col in range(n):
            if not self.isValid(row,col,temp,n):
                continue
            temp[row][col]='Q'
            self.backtrack(n,row+1,temp)
            temp[row][col]='.'
    
    def isValid(self,row,col,temp,n):
        #判断上方是否有皇后出没
        for r in range(row):
            if temp[r][col]=='Q':
                return False

        #判断左上方是否有皇后出没
        r1,c1=row-1,col-1
        while r1>=0 and c1>=0:
            if temp[r1][c1]=='Q':
                return False
            r1-=1
            c1-=1

        #判断右上方是否有皇后出没
        r2,c2=row-1,col+1
        while r2>=0 and c2<n:
            if temp[r2][c2]=='Q':
                return False
            r2-=1
            c2+=1
        return True

[simplesboy]

判断列上边是否有皇后，感觉不需要小于n，小于当前层row就可以了，和不用判断左下右下一个原因

[JiaqiFlora]

请问一下大家，对于这个问题，有没有一个比较好记忆的理解： 这个回溯的时候，添加和去除是在for循环里面，但是前文中图算法中的环检测（course schedule）的题中，添加和去除是在for循环外面的。不是很理解，为什么一个在里面，一个在外面。单看每一种算法，我可以理解，但是为什么两个问题的处理方法不一样呢？谢谢大家！

[Link-GZJ]

// 检查列是否有皇后互相冲突
for (int i = 0; i <= row; i++) {
    if (board[i][col] == 'Q')
        return false;
}

这里直接小于row,第row行不用判断，对不对？因为就是要放到这一行的

[doublebridge]

每次写backtracking没啥问题，但一问complexity就卡壳，尤其是变种题或者有直接数学方法求组合数的题

[John520]

邮件已收到，谢谢。   华南理工大学2015级控制理论与控制工程           徐将将            tel：13560349491（629491）            地址：华工（五三

[zixiangcode]

在 “全排列问题” 的 C++ 解题方案中，作者用的是 vector<bool> used(nums.size(), false); ，但是事实上，并不推荐使用 std::vector<bool>，因为它并不是通俗意义上的 STL 容器，std::vector<bool> 的存储是按照位存储的，也就是说 std::vector 对 bool 类型进行了空间优化，它的每个元素的存储并不再是一个 sizeof(bool) 。

譬如对于下面的代码：

std::vector<bool> a = { false, true, false };
auto b = a[0];
bool c = a[0];

对于变量 c 的初始化，其实暗含了一个隐式的类型转换。而对于变量 b，它的类型并不是 bool，而是一个代理对象，也就是 std::vector<bool>::reference 类型。所以此时如果修改 b 的值，a 中的值也会跟着修改。

当然就 LeetCode 而言，这样用并不会报错，但是仍然不推荐这样使用。如果想使用 std::vector<bool> 可以考虑采用 std::bitset 或 boost::dynamic_bitset 替代（当然 LeetCode 并没有引入 boost 库），也可以采用 std::deque<bool>。更多内容可以参考 std::vector