关于算法:回溯算法解题套路框架

读完本文，你能够去力扣拿下如下题目：

46. 全排列

51.N 皇后

———–

这篇文章是很久之前的一篇《回溯算法详解》的进阶版，之前那篇不够分明，就不用看了，看这篇就行。把框架给你讲清楚，你会发现回溯算法问题都是一个套路。

废话不多说，间接上回溯算法框架。 解决一个回溯问题，实际上就是一个决策树的遍历过程 。你只须要思考 3 个问题：

1、门路：也就是曾经做出的抉择。

2、抉择列表：也就是你以后能够做的抉择。

3、完结条件：也就是达到决策树底层，无奈再做抉择的条件。

如果你不了解这三个词语的解释，没关系，咱们前面会用「全排列」和「N 皇后问题」这两个经典的回溯算法问题来帮你了解这些词语是什么意思，当初你先留着印象。

代码方面，回溯算法的框架：

result = []
def backtrack(门路, 抉择列表):
    if 满足完结条件:
        result.add(门路)
        return
    
    for 抉择 in 抉择列表:
        做抉择
        backtrack(门路, 抉择列表)
        撤销抉择 

其外围就是 for 循环外面的递归，在递归调用之前「做抉择」，在递归调用之后「撤销抉择」，特地简略。

什么叫做抉择和撤销抉择呢，这个框架的底层原理是什么呢？上面咱们就通过「全排列」这个问题来解开之前的纳闷，具体探索一下其中的奥秘！

一、全排列问题

咱们在高中的时候就做过排列组合的数学题，咱们也晓得 n 个不反复的数，全排列共有 n! 个。

PS： 为了简略清晰起见，咱们这次探讨的全排列问题不蕴含反复的数字 。

那么咱们过后是怎么穷举全排列的呢？比方说给三个数 [1,2,3]，你必定不会无规律地乱穷举，个别是这样：

先固定第一位为 1，而后第二位能够是 2，那么第三位只能是 3；而后能够把第二位变成 3，第三位就只能是 2 了；而后就只能变动第一位，变成 2，而后再穷举后两位……

其实这就是回溯算法，咱们高中无师自通就会用，或者有的同学间接画出如下这棵回溯树：

只有从根遍历这棵树，记录门路上的数字，其实就是所有的全排列。 咱们无妨把这棵树称为回溯算法的「决策树」。

为啥说这是决策树呢，因为你在每个节点上其实都在做决策 。比如说你站在下图的红色节点上：

你当初就在做决策，能够抉择 1 那条树枝，也能够抉择 3 那条树枝。为啥只能在 1 和 3 之中抉择呢？因为 2 这个树枝在你身后，这个抉择你之前做过了，而全排列是不容许重复使用数字的。

当初能够解答结尾的几个名词：[2] 就是「门路」，记录你曾经做过的抉择；[1,3] 就是「抉择列表」，示意你以后能够做出的抉择；「完结条件」就是遍历到树的底层，在这里就是抉择列表为空的时候 。

如果明确了这几个名词， 能够把「门路」和「抉择」列表作为决策树上每个节点的属性 ，比方下图列出了几个节点的属性：

咱们定义的 backtrack 函数其实就像一个指针，在这棵树上游走，同时要正确保护每个节点的属性，每当走到树的底层，其「门路」就是一个全排列 。

再进一步，如何遍历一棵树？这个应该不难吧。回顾一下之前「学习数据结构的框架思维」写过，各种搜寻问题其实都是树的遍历问题，而多叉树的遍历框架就是这样：

void traverse(TreeNode root) {for (TreeNode child : root.childern)
        // 前序遍历须要的操作
        traverse(child);
        // 后序遍历须要的操作
}

而所谓的前序遍历和后序遍历，他们只是两个很有用的工夫点，我给你画张图你就明确了：

前序遍历的代码在进入某一个节点之前的那个工夫点执行，后序遍历代码在来到某个节点之后的那个工夫点执行 。

回忆咱们方才说的，「门路」和「抉择」是每个节点的属性，函数在树上游走要正确保护节点的属性，那么就要在这两个非凡工夫点搞点动作：

当初，你是否了解了回溯算法的这段外围框架？

for 抉择 in 抉择列表:
    # 做抉择
    将该抉择从抉择列表移除
    门路.add(抉择)
    backtrack(门路, 抉择列表)
    # 撤销抉择
    门路.remove(抉择)
    将该抉择再退出抉择列表 

咱们只有在递归之前做出抉择，在递归之后撤销方才的抉择 ，就能正确失去每个节点的抉择列表和门路。

上面，间接看全排列代码：

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

/* 主函数，输出一组不反复的数字，返回它们的全排列 */
List<List<Integer>> permute(int[] nums) {
    // 记录「门路」LinkedList<Integer> track = new LinkedList<>();
    backtrack(nums, track);
    return res;
}

// 门路：记录在 track 中
// 抉择列表：nums 中不存在于 track 的那些元素
// 完结条件：nums 中的元素全都在 track 中呈现
void backtrack(int[] nums, LinkedList<Integer> track) {
    // 触发完结条件
    if (track.size() == nums.length) {res.add(new LinkedList(track));
        return;
    }
    
    for (int i = 0; i < nums.length; i++) {
        // 排除不非法的抉择
        if (track.contains(nums[i]))
            continue;
        // 做抉择
        track.add(nums[i]);
        // 进入下一层决策树
        backtrack(nums, track);
        // 勾销抉择
        track.removeLast();}
}

咱们这里略微做了些变通，没有显式记录「抉择列表」，而是通过 nums 和 track 推导出以后的抉择列表：

至此，咱们就通过全排列问题详解了回溯算法的底层原理。当然，这个算法解决全排列不是很高效，应为对链表应用 contains 办法须要 O(N) 的工夫复杂度。有更好的办法通过替换元素达到目标，然而难了解一些，这里就不写了，有趣味能够自行搜寻一下。

然而必须阐明的是，不管怎么优化，都合乎回溯框架，而且工夫复杂度都不可能低于 O(N!)，因为穷举整棵决策树是无奈防止的。 这也是回溯算法的一个特点，不像动静布局存在重叠子问题能够优化，回溯算法就是纯暴力穷举，复杂度个别都很高 。

明确了全排列问题，就能够间接套回溯算法框架了，上面简略看看 N 皇后问题。

二、N 皇后问题

这个问题很经典了，简略解释一下：给你一个 N×N 的棋盘，让你搁置 N 个皇后，使得它们不能互相攻击。

PS：皇后能够攻打同一行、同一列、左上左下右上右下四个方向的任意单位。

这个问题实质上跟全排列问题差不多，决策树的每一层示意棋盘上的每一行；每个节点能够做出的抉择是，在该行的任意一列搁置一个皇后。

间接套用框架:

vector<vector<string>> res;

/* 输出棋盘边长 n，返回所有非法的搁置 */
vector<vector<string>> solveNQueens(int n) {
    // '.' 示意空，'Q' 示意皇后，初始化空棋盘。vector<string> board(n, string(n, '.'));
    backtrack(board, 0);
    return res;
}

// 门路：board 中小于 row 的那些行都曾经胜利搁置了皇后
// 抉择列表：第 row 行的所有列都是搁置皇后的抉择
// 完结条件：row 超过 board 的最初一行
void backtrack(vector<string>& board, int row) {
    // 触发完结条件
    if (row == board.size()) {res.push_back(board);
        return;
    }
    
    int n = board[row].size();
    for (int col = 0; col < n; col++) {
        // 排除不非法抉择
        if (!isValid(board, row, col)) 
            continue;
        // 做抉择
        board[row][col] = 'Q';
        // 进入下一行决策
        backtrack(board, row + 1);
        // 撤销抉择
        board[row][col] = '.';
    }
}

这部分次要代码，其实跟全排列问题差不多，isValid 函数的实现也很简略：

/* 是否能够在 board[row][col] 搁置皇后？*/
bool isValid(vector<string>& board, int row, int col) {int n = board.size();
    // 查看列是否有皇后互相冲突
    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;
}

函数 backtrack 仍然像个在决策树上游走的指针，通过 row 和 col 就能够示意函数遍历到的地位，通过 isValid 函数能够将不符合条件的状况剪枝：

如果间接给你这么一大段解法代码，可能是懵逼的。然而当初明确了回溯算法的框架套路，还有啥难了解的呢？无非是改改做抉择的形式，排除不非法抉择的形式而已，只有框架存于心，你面对的只剩下小问题了。

当 N = 8 时，就是八皇后问题，数学大佬高斯穷尽毕生都没有数分明八皇后问题到底有几种可能的搁置办法，然而咱们的算法只须要一秒就能够算进去所有可能的后果。

不过真的不怪高斯。这个问题的复杂度的确十分高，看看咱们的决策树，尽管有 isValid 函数剪枝，然而最坏工夫复杂度依然是 O(N^(N+1))，而且无奈优化。如果 N = 10 的时候，计算就曾经很耗时了。

有的时候，咱们并不想失去所有非法的答案，只想要一个答案，怎么办呢 ？比方解数独的算法，找所有解法复杂度太高，只有找到一种解法就能够。

其实特地简略，只有略微批改一下回溯算法的代码即可：

// 函数找到一个答案后就返回 true
bool backtrack(vector<string>& board, int row) {
    // 触发完结条件
    if (row == board.size()) {res.push_back(board);
        return true;
    }
    ...
    for (int col = 0; col < n; col++) {
        ...
        board[row][col] = 'Q';

        if (backtrack(board, row + 1))
            return true;
        
        board[row][col] = '.';
    }

    return false;
}

这样批改后，只有找到一个答案，for 循环的后续递归穷举都会被阻断。兴许你能够在 N 皇后问题的代码框架上，稍加批改，写一个解数独的算法？

三、最初总结

回溯算法就是个多叉树的遍历问题，要害就是在前序遍历和后序遍历的地位做一些操作，算法框架如下：

def backtrack(...):
    for 抉择 in 抉择列表:
        做抉择
        backtrack(...)
        撤销抉择 

写 backtrack 函数时，须要保护走过的「门路」和以后能够做的「抉择列表」，当触发「完结条件」时，将「门路」记入后果集 。

其实想想看，回溯算法和动静布局是不是有点像呢？咱们在动静布局系列文章中屡次强调，动静布局的三个须要明确的点就是「状态」「抉择」和「base case」，是不是就对应着走过的「门路」，以后的「抉择列表」和「完结条件」？

某种程度上说，动静布局的暴力求解阶段就是回溯算法。只是有的问题具备重叠子问题性质，能够用 dp table 或者备忘录优化，将递归树大幅剪枝，这就变成了动静布局。而明天的两个问题，都没有重叠子问题，也就是回溯算法问题了，复杂度十分高是不可避免的。