原文作者：labuladong

原文地址：回溯算法套路詳解

讀完本文，你可以去力扣拿下如下題目：

46.全排列

51.N皇后

解決一個(gè)回溯問題，實(shí)際上就是一個(gè)決策樹的遍歷過程。你只需要思考 3 個(gè)問題：

• 1、路徑：也就是已經(jīng)做出的選擇。
• 2、選擇列表：也就是你當(dāng)前可以做的選擇。
• 3、結(jié)束條件：也就是到達(dá)決策樹底層，無法再做選擇的條件。

如果你不理解這三個(gè)詞語的解釋，沒關(guān)系，我們后面會(huì)用「全排列」和「N 皇后問題」這兩個(gè)經(jīng)典的回溯算法問題來幫你理解這些詞語是什么意思，現(xiàn)在你先留著印象。代碼方面，回溯算法的框架：

result = [] def backtrack(路徑, 選擇列表):if 滿足結(jié)束條件:result.add(路徑)returnfor 選擇 in 選擇列表:做選擇backtrack(路徑, 選擇列表)撤銷選擇

其核心就是 for 循環(huán)里面的遞歸，在遞歸調(diào)用之前「做選擇」，在遞歸調(diào)用之后「撤銷選擇」，特別簡(jiǎn)單。什么叫做選擇和撤銷選擇呢，這個(gè)框架的底層原理是什么呢？下面我們就通過「全排列」這個(gè)問題來解開之前的疑惑，詳細(xì)探究一下其中的奧妙！

一、全排列問題

我們?cè)诟咧械臅r(shí)候就做過排列組合的數(shù)學(xué)題，我們也知道?n?個(gè)不重復(fù)的數(shù)，全排列共有 n! 個(gè)。PS：為了簡(jiǎn)單清晰起見，我們這次討論的全排列問題不包含重復(fù)的數(shù)字。那么我們當(dāng)時(shí)是怎么窮舉全排列的呢？比方說給三個(gè)數(shù)?[1,2,3]，你肯定不會(huì)無規(guī)律地亂窮舉，一般是這樣：先固定第一位為 1，然后第二位可以是 2，那么第三位只能是 3；然后可以把第二位變成 3，第三位就只能是 2 了；然后就只能變化第一位，變成 2，然后再窮舉后兩位……其實(shí)這就是回溯算法，我們高中無師自通就會(huì)用，或者有的同學(xué)直接畫出如下這棵回溯樹：

只要從根遍歷這棵樹，記錄路徑上的數(shù)字，其實(shí)就是所有的全排列。我們不妨把這棵樹稱為回溯算法的「決策樹」。為啥說這是決策樹呢，因?yàn)槟阍诿總€(gè)節(jié)點(diǎn)上其實(shí)都在做決策。比如說你站在下圖的紅色節(jié)點(diǎn)上：

你現(xiàn)在就在做決策，可以選擇 1 那條樹枝，也可以選擇 3 那條樹枝。為啥只能在 1 和 3 之中選擇呢？因?yàn)?2 這個(gè)樹枝在你身后，這個(gè)選擇你之前做過了，而全排列是不允許重復(fù)使用數(shù)字的。現(xiàn)在可以解答開頭的幾個(gè)名詞：[2]?就是「路徑」，記錄你已經(jīng)做過的選擇；[1,3]?就是「選擇列表」，表示你當(dāng)前可以做出的選擇；「結(jié)束條件」就是遍歷到樹的底層，在這里就是選擇列表為空的時(shí)候。如果明白了這幾個(gè)名詞，可以把「路徑」和「選擇」列表作為決策樹上每個(gè)節(jié)點(diǎn)的屬性，比如下圖列出了幾個(gè)節(jié)點(diǎn)的屬性：

我們定義的?backtrack?函數(shù)其實(shí)就像一個(gè)指針，在這棵樹上游走，同時(shí)要正確維護(hù)每個(gè)節(jié)點(diǎn)的屬性，每當(dāng)走到樹的底層，其「路徑」就是一個(gè)全排列。再進(jìn)一步，如何遍歷一棵樹？這個(gè)應(yīng)該不難吧?；貞浺幌轮啊笇W(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的框架思維」寫過，各種搜索問題其實(shí)都是樹的遍歷問題，而多叉樹的遍歷框架就是這樣：

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

而所謂的前序遍歷和后序遍歷，他們只是兩個(gè)很有用的時(shí)間點(diǎn)，我給你畫張圖你就明白了：

前序遍歷的代碼在進(jìn)入某一個(gè)節(jié)點(diǎn)之前的那個(gè)時(shí)間點(diǎn)執(zhí)行，后序遍歷代碼在離開某個(gè)節(jié)點(diǎn)之后的那個(gè)時(shí)間點(diǎn)執(zhí)行?；叵胛覀儎偛耪f的，「路徑」和「選擇」是每個(gè)節(jié)點(diǎn)的屬性，函數(shù)在樹上游走要正確維護(hù)節(jié)點(diǎn)的屬性，那么就要在這兩個(gè)特殊時(shí)間點(diǎn)搞點(diǎn)動(dòng)作：

現(xiàn)在，你是否理解了回溯算法的這段核心框架？

for 選擇 in 選擇列表:# 做選擇將該選擇從選擇列表移除路徑.add(選擇)backtrack(路徑, 選擇列表)# 撤銷選擇路徑.remove(選擇)將該選擇再加入選擇列表

我們只要在遞歸之前做出選擇，在遞歸之后撤銷剛才的選擇，就能正確得到每個(gè)節(jié)點(diǎn)的選擇列表和路徑。下面，直接看全排列代碼：

List<List<Integer>> res = new LinkedList<>();/* 主函數(shù)，輸入一組不重復(fù)的數(shù)字，返回它們的全排列 */ List<List<Integer>> permute(int[] nums) {// 記錄「路徑」LinkedList<Integer> track = new LinkedList<>();backtrack(nums, track);return res; }// 路徑：記錄在 track 中 // 選擇列表：nums 中不存在于 track 的那些元素 // 結(jié)束條件：nums 中的元素全都在 track 中出現(xiàn) void backtrack(int[] nums, LinkedList<Integer> track) {// 觸發(fā)結(jié)束條件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]);// 進(jìn)入下一層決策樹backtrack(nums, track);// 取消選擇track.removeLast();} }

我們這里稍微做了些變通，沒有顯式記錄「選擇列表」，而是通過?nums?和?track?推導(dǎo)出當(dāng)前的選擇列表：

至此，我們就通過全排列問題詳解了回溯算法的底層原理。當(dāng)然，這個(gè)算法解決全排列不是很高效，應(yīng)為對(duì)鏈表使用?contains?方法需要 O(N) 的時(shí)間復(fù)雜度。有更好的方法通過交換元素達(dá)到目的，但是難理解一些，這里就不寫了，有興趣可以自行搜索一下。但是必須說明的是，不管怎么優(yōu)化，都符合回溯框架，而且時(shí)間復(fù)雜度都不可能低于 O(N!)，因?yàn)楦F舉整棵決策樹是無法避免的。這也是回溯算法的一個(gè)特點(diǎn)，不像動(dòng)態(tài)規(guī)劃存在重疊子問題可以優(yōu)化，回溯算法就是純暴力窮舉，復(fù)雜度一般都很高。明白了全排列問題，就可以直接套回溯算法框架了，下面簡(jiǎn)單看看 N 皇后問題。PS：我認(rèn)真寫了 100 多篇原創(chuàng)，手把手刷 200 道力扣題目，全部發(fā)布在?labuladong的算法小抄，持續(xù)更新。建議收藏，按照我的文章順序刷題，掌握各種算法套路后投再入題海就如魚得水了。

二、N 皇后問題

這個(gè)問題很經(jīng)典了，簡(jiǎn)單解釋一下：給你一個(gè) N×N 的棋盤，讓你放置 N 個(gè)皇后，使得它們不能互相攻擊。PS：皇后可以攻擊同一行、同一列、左上左下右上右下四個(gè)方向的任意單位。這個(gè)問題本質(zhì)上跟全排列問題差不多，決策樹的每一層表示棋盤上的每一行；每個(gè)節(jié)點(diǎn)可以做出的選擇是，在該行的任意一列放置一個(gè)皇后。直接套用框架:

?

總結(jié)

以上是生活随笔為你收集整理的五大常用经典算法—回溯算法的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。