55utah / leetcode Goto Github PK

46.全排列
51.N 皇后

回溯本质就是DFS算法，属于暴力穷举算法，也就是在做一个决策树的遍历，一般与递归结合。

参考：https://labuladong.github.io/algo/1/4/

result = []
def backtrack(路径, 选择列表):
    if 满足结束条件:
        result.add(路径)
        return
    
    for 选择 in 选择列表:
        做选择
        backtrack(路径, 选择列表)

function solve() {
    const result = []
    const go = () => {
         // 判断满足条件
         if (solved) result.push(xxx); return;
         // 做选择，排除不合理选择，进入下一层决策树
         // 遍历子情况，递归处理
         for () {
            go()
         // 有时需要根据上面结果做选择，比如const bool = go(); if (bool) break; 
         // 下一层的其中一个决策树有结果之后，可以停止更多计算，达到剪枝的目的；
         // 这种方法适合于只需寻找一个答案的情况，在找到后停止遍历。
         }
    }
    return result
}

// Typescript版本的回溯法

function solveNQueens(n: number): string[][] {
    if (n == 1) return [['Q']]
    // n个皇后放在n*n的网格内，必定是一行一个，使用一维数组处理
    // 避免通常思维的二维数组，存在复杂度高、引用类型等问题
    // 利用特性降低计算难度，降为一维数组（默认满足了每个皇后左右直线不能有皇后的条件）
    const result = []

    // 使用回溯法思路，从上到下按行遍历，每一行判断棋子可放在哪个位置，然后迭代
    const go = (rows: number[], count: number) => {
        // 已经是n个棋子返回
        if (count >= n) {
            result.push(rows)
            return true
        }
        // 遍历当前行每个位置
        for (let i = 0; i < n; i++) {
            // 斜对角直线上所有位置都不能有棋子
            // 判断 (count, i) 与 (k, j) 元素判断是否对角线 + 本列是否有棋子
            // 满足上下和对角线不能有棋子要求
            const invalid = rows.some((j, k) => Math.abs(count - k) === Math.abs(i - j) || j === i)
            if (!invalid) {
                // 进入下一层迭代
                go(rows.concat(i), count + 1)
            }
        }
    }
    // 初始化数据执行
    go([], 0)
    // 最后再组装输出
    return result.map((row) => {
        return row.map(p => {
            const arr = new Array(n).fill('.')
            arr[p] = 'Q'
            return arr.join('')
        })
    })
};