3、回溯算法解题套路框架——Go语言版
前情提示：Go語言學習者。本文參考https://labuladong.gitee.io/algo，代碼自己參考抒寫，若有不妥之處，感謝指正
關于golang算法文章，為了便于下載和整理，都已開源放在：
- https://github.com/honlu/GoLabuladongAlgorithm
- https://gitee.com/dreamzll/GoLabuladongAlgorithm
方便就請分享，star！備注轉載地址！歡迎一起學習和交流！
涉及題目
- 46. 全排列（中等）
- 51. N皇后（困難）
回溯算法其實就是我們常說的 DFS 算法，本質上就是一種暴力窮舉算法。
廢話不多說，直接上回溯算法框架。解決一個回溯問題，實際上就是一個決策樹的遍歷過程。你只需要思考 3 個問題：
1、路徑：也就是已經做出的選擇。
2、選擇列表：也就是你當前可以做的選擇。
3、結束條件：也就是到達決策樹底層，無法再做選擇的條件。
如果你不理解這三個詞語的解釋，沒關系，我們后面會用「全排列」和「N 皇后問題」這兩個經典的回溯算法問題來幫你理解這些詞語是什么意思，現在你先留著印象。
代碼方面，回溯算法的框架：
// 偽碼
var res [][]int
func backTrack(路徑，選擇列表){
if 滿足結束條件{ // 終止條件
res = append(res, 路徑) // 存放結果
return
}
for _,選擇 := range 選擇列表{ // 選擇：本層集合中元素（樹中節點孩子的數量就是集合的大小）
做選擇 // 處理節點
backTrack(路徑，選擇列表) // 遞歸
撤銷選擇 // 回溯，撤銷處理結果
}
}
其核心就是 for 循環里面的遞歸，在遞歸調用之前「做選擇」，在遞歸調用之后「撤銷選擇」，特別簡單。
什么叫做選擇和撤銷選擇呢，這個框架的底層原理是什么呢？下面我們就通過「全排列」這個問題來解開之前的疑惑，詳細探究一下其中的奧妙！
一、全排列問題
我們在高中的時候就做過排列組合的數學題，我們也知道 n 個不重復的數，全排列共有 n! 個。
PS：為了簡單清晰起見，我們這次討論的全排列問題不包含重復的數字。
那么我們當時是怎么窮舉全排列的呢？比方說給三個數 [1,2,3]，你肯定不會無規律地亂窮舉，一般是這樣：
先固定第一位為 1，然后第二位可以是 2，那么第三位只能是 3；然后可以把第二位變成 3，第三位就只能是 2 了；然后就只能變化第一位，變成 2，然后再窮舉后兩位……
其實這就是回溯算法，我們高中無師自通就會用，或者有的同學直接畫出如下這棵回溯樹：
只要從根遍歷這棵樹，記錄路徑上的數字，其實就是所有的全排列。我們不妨把這棵樹稱為回溯算法的「決策樹」。
為啥說這是決策樹呢，因為你在每個節點上其實都在做決策。比如說你站在下圖的紅色節點上：
你現在就在做決策，可以選擇 1 那條樹枝，也可以選擇 3 那條樹枝。為啥只能在 1 和 3 之中選擇呢？因為 2 這個樹枝在你身后，這個選擇你之前做過了，而全排列是不允許重復使用數字的。
現在可以解答開頭的幾個名詞：[2] 就是「路徑」，記錄你已經做過的選擇；[1,3] 就是「選擇列表」，表示你當前可以做出的選擇；「結束條件」就是遍歷到樹的底層，在這里就是選擇列表為空的時候。
如果明白了這幾個名詞，可以把「路徑」和「選擇」列表作為決策樹上每個節點的屬性，比如下圖列出了幾個節點的屬性：
我們定義的 backtrack 函數其實就像一個指針，在這棵樹上游走，同時要正確維護每個節點的屬性，每當走到樹的底層，其「路徑」就是一個全排列。
再進一步，如何遍歷一棵樹？這個應該不難吧。回憶一下之前 學習數據結構的框架思維 寫過，各種搜索問題其實都是樹的遍歷問題，而多叉樹的遍歷框架就是這樣：
// 偽碼
func traverse(root *TreeNode){
for _, child := range root.children{
// 前序遍歷需要的操作
traverse(child)
// 后序遍歷需要的操作
}
}
而所謂的前序遍歷和后序遍歷，他們只是兩個很有用的時間點，我給你畫張圖你就明白了：
前序遍歷的代碼在進入某一個節點之前的那個時間點執行，后序遍歷代碼在離開某個節點之后的那個時間點執行。
回想我們剛才說的，「路徑」和「選擇」是每個節點的屬性，函數在樹上游走要正確維護節點的屬性，那么就要在這兩個特殊時間點搞點動作：
現在，你是否理解了回溯算法的這段核心框架？
var res [][]int
// 主函數，輸入一組不重復的數字，返回他們的全排列
func permute(nums []int) [][]int {
// 記錄"路徑"
res = [][]int{}
var track []int
backTrack(nums, track)
return res
}
// 路徑：記錄在track中
// 選擇列表：nums中不存在于track的那些元素
// 結束條件：nums中的元素全都在track中出現
func backTrack(nums []int, track []int) {
if len(nums) == 0 {
p := make([]int, len(track))
copy(p, track) // 學習新函數
res = append(res, p)
}
for i := 0; i < len(nums); i++ {
// 做選擇
cur := nums[i]
track = append(track, nums[i])
nums = append(nums[:i],nums[i+1:]...)//直接使用切片，刪除nums[i]
// 進入下一層決策樹
backTrack(nums, track)
// 取消選擇,刪除最后一個元素
nums = append(nums[:i],append([]int{cur},nums[i:]...)...)//回溯的時候切片也要復原，元素位置不能變
track = track[:len(track)-1]
}
}
我們這里稍微做了些變通，沒有顯式記錄「選擇列表」，而是通過 nums 和 track 推導出當前的選擇列表：
至此，我們就通過全排列問題詳解了回溯算法的底層原理。當然，這個算法解決全排列不是很高效，應為對鏈表使用 contains 方法需要 O(N) 的時間復雜度。有更好的方法通過交換元素達到目的，但是難理解一些，這里就不寫了，有興趣可以自行搜索一下。
但是必須說明的是，不管怎么優化，都符合回溯框架，而且時間復雜度都不可能低于 O(N!)，因為窮舉整棵決策樹是無法避免的。這也是回溯算法的一個特點，不像動態規劃存在重疊子問題可以優化，回溯算法就是純暴力窮舉，復雜度一般都很高。
明白了全排列問題，就可以直接套回溯算法框架了，下面簡單看看 N 皇后問題。
二、N 皇后問題
這個問題很經典了，簡單解釋一下：給你一個 N×N 的棋盤，讓你放置 N 個皇后，使得它們不能互相攻擊。
PS：皇后可以攻擊同一行、同一列、左上左下右上右下四個方向的任意單位。
這個問題本質上跟全排列問題差不多，決策樹的每一層表示棋盤上的每一行；每個節點可以做出的選擇是，在該行的任意一列放置一個皇后。
直接套用回溯算法框架:
import "strings"
var res [][]string
// 輸入棋盤邊長n, 返回所有合法的放置方法
func solveNQueens(n int) [][]string {
res = [][]string{}
// 棋盤定義和初始化
board := make([][]string, n)
for i := 0; i < n; i++ {
board[i] = make([]string, n)
}
for i := 0; i < n; i++ {
for j := 0; j < n; j++ {
board[i][j] = "."
}
}
// 回溯
backTrack(board, 0)
return res
}
// 路徑：board中小于row的那些行都已經成功放置了皇后
// 選擇列表：第row行的所有列都是放置皇后的選擇
// 結束條件：row超過board的最后一行，說明棋盤滿了
func backTrack(board [][]string, row int) {
// 觸發結束條件
size := len(board)
if row == size {
temp := make([]string, size) // 保存一種棋盤解法
for i := 0; i < size; i++ { // 將棋盤n*n 轉為n*1的數組
temp[i] = strings.Join(board[i], "") // 將第i行的結果，連接起來
}
res = append(res, temp)
return
}
for col := 0; col < size; col++ {
// 排除不合法選擇
if !isValid(board, row, col) {
continue
}
// 做選擇
board[row][col] = "Q"
// 進入下一行決策
backTrack(board, row+1)
// 撤銷選擇
board[row][col] = "."
}
}
這部分主要代碼，其實跟全排列問題差不多。isValid 函數的實現也很簡單：
// 判斷是否可以在board[row][col]放置皇后
func isValid(board [][]string, row, col int) bool {
n := len(board)
// 檢查列中是否有皇后互相沖突
for i := 0; i < row; i++ {
if board[i][col] == "Q" {
return false
}
}
// 檢查右上方是否有皇后互相沖突
for i, j := row-1, col+1; i >= 0 && j < n; i, j = i-1, j+1 {
if board[i][j] == "Q" {
return false
}
}
// 檢查左上方是否有皇后互相沖突
for i, j := row-1, col-1; i >= 0 && j >= 0; i, j = i-1, j-1 {
if board[i][j] == "Q" {
return false
}
}
return true
}
PS：肯定有讀者問，按照 N 皇后問題的描述，我們為什么不檢查左下角，右下角和下方的格子，只檢查了左上角，右上角和上方的格子呢？
因為皇后是一行一行從上往下放的，所以左下方，右下方和正下方不用檢查（還沒放皇后）；因為一行只會放一個皇后，所以每行不用檢查。也就是最后只用檢查上面，左上，右上三個方向。
函數 backtrack 依然像個在決策樹上游走的指針，通過 row 和 col 就可以表示函數遍歷到的位置，通過 isValid 函數可以將不符合條件的情況剪枝：
如果直接給你這么一大段解法代碼，可能是懵逼的。但是現在明白了回溯算法的框架套路，還有啥難理解的呢？無非是改改做選擇的方式，排除不合法選擇的方式而已，只要框架存于心，你面對的只剩下小問題了。
當 N = 8 時，就是八皇后問題，數學大佬高斯窮盡一生都沒有數清楚八皇后問題到底有幾種可能的放置方法，但是我們的算法只需要一秒就可以算出來所有可能的結果。
不過真的不怪高斯。這個問題的復雜度確實非常高，看看我們的決策樹，雖然有 isValid 函數剪枝，但是最壞時間復雜度仍然是 O(N^(N+1))，而且無法優化。如果 N = 10 的時候，計算就已經很耗時了。
有的時候，我們并不想得到所有合法的答案，只想要一個答案，怎么辦呢？比如解數獨的算法，找所有解法復雜度太高，只要找到一種解法就可以。
其實特別簡單，只要稍微修改一下回溯算法的代碼即可：
func backTrack(board [][]string, row int) bool{
// 觸發結束條件
size := len(board)
if row == size {
temp := make([]string, size) // 保存一種棋盤解法
for i := 0; i < size; i++ { // 將棋盤n*n 轉為n*1的數組
temp[i] = strings.Join(board[i], "") // 將第i行的結果，連接起來
}
res = append(res, temp)
return true
}
for col := 0; col < size; col++ {
// 排除不合法選擇
if !isValid(board, row, col) {
continue
}
// 做選擇
board[row][col] = "Q"
// 進入下一行決策
if backTrack(board, row+1){
return true
}
// 撤銷選擇
board[row][col] = "."
}
}
這樣修改后，只要找到一個答案，for 循環的后續遞歸窮舉都會被阻斷。也許你可以在 N 皇后問題的代碼框架上，稍加修改，寫一個解數獨的算法？
三、最后總結
回溯算法就是個多叉樹的遍歷問題，關鍵就是在前序遍歷和后序遍歷的位置做一些操作，算法框架如下：
func backTrack(參數) {
if (終止條件) {
存放結果;
return;
}
for (選擇：本層集合中元素（樹中節點孩子的數量就是集合的大小）) {
處理節點;
backTrack(路徑，選擇列表); // 遞歸
回溯，撤銷處理結果
}
}
寫 backtrack 函數時，需要維護走過的「路徑」和當前可以做的「選擇列表」，當觸發「結束條件」時，將「路徑」記入結果集。
其實想想看，回溯算法和動態規劃是不是有點像呢？我們在動態規劃系列文章中多次強調，動態規劃的三個需要明確的點就是「狀態」「選擇」和「base case」，是不是就對應著走過的「路徑」，當前的「選擇列表」和「結束條件」？
某種程度上說，動態規劃的暴力求解階段就是回溯算法。只是有的問題具有重疊子問題性質，可以用 dp table 或者備忘錄優化，將遞歸樹大幅剪枝，這就變成了動態規劃。而今天的兩個問題，都沒有重疊子問題，也就是回溯算法問題了，復雜度非常高是不可避免的。
總結
以上是生活随笔為你收集整理的3、回溯算法解题套路框架——Go语言版的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 通用三缸发动机怎么样 评测通用三缸发动机
- 下一篇： 14款奥迪q3可以投屏导航吗？