讀完本文，你可以去力扣拿下如下題目：
-----------
這篇文章是很久之前的一篇《回溯算法詳解》的進(jìn)階版金顿，之前那篇不夠清楚仿荆，就不必看了贰您，看這篇就行。把框架給你講清楚拢操，你會(huì)發(fā)現(xiàn)回溯算法問(wèn)題都是一個(gè)套路锦亦。
廢話(huà)不多說(shuō)，直接上回溯算法框架令境。解決一個(gè)回溯問(wèn)題杠园，實(shí)際上就是一個(gè)決策樹(shù)的遍歷過(guò)程。你只需要思考 3 個(gè)問(wèn)題：
1展父、路徑：也就是已經(jīng)做出的選擇返劲。
2、選擇列表：也就是你當(dāng)前可以做的選擇栖茉。
3篮绿、結(jié)束條件：也就是到達(dá)決策樹(shù)底層，無(wú)法再做選擇的條件吕漂。
如果你不理解這三個(gè)詞語(yǔ)的解釋?zhuān)瑳](méi)關(guān)系亲配，我們后面會(huì)用「全排列」和「N 皇后問(wèn)題」這兩個(gè)經(jīng)典的回溯算法問(wèn)題來(lái)幫你理解這些詞語(yǔ)是什么意思，現(xiàn)在你先留著印象惶凝。
代碼方面吼虎，回溯算法的框架：
result = []
def backtrack(路徑, 選擇列表):
if 滿(mǎn)足結(jié)束條件:
result.add(路徑)
return
for 選擇 in 選擇列表:
做選擇
backtrack(路徑, 選擇列表)
撤銷(xiāo)選擇
其核心就是 for 循環(huán)里面的遞歸，在遞歸調(diào)用之前「做選擇」苍鲜，在遞歸調(diào)用之后「撤銷(xiāo)選擇」思灰，特別簡(jiǎn)單。
什么叫做選擇和撤銷(xiāo)選擇呢混滔，這個(gè)框架的底層原理是什么呢洒疚？下面我們就通過(guò)「全排列」這個(gè)問(wèn)題來(lái)解開(kāi)之前的疑惑歹颓，詳細(xì)探究一下其中的奧妙！
一油湖、全排列問(wèn)題
我們?cè)诟咧械臅r(shí)候就做過(guò)排列組合的數(shù)學(xué)題巍扛，我們也知道 n 個(gè)不重復(fù)的數(shù)，全排列共有 n! 個(gè)乏德。
PS：為了簡(jiǎn)單清晰起見(jiàn)撤奸，我們這次討論的全排列問(wèn)題不包含重復(fù)的數(shù)字。
那么我們當(dāng)時(shí)是怎么窮舉全排列的呢喊括？比方說(shuō)給三個(gè)數(shù) [1,2,3]胧瓜，你肯定不會(huì)無(wú)規(guī)律地亂窮舉，一般是這樣：
先固定第一位為 1郑什，然后第二位可以是 2贷痪，那么第三位只能是 3；然后可以把第二位變成 3蹦误，第三位就只能是 2 了劫拢；然后就只能變化第一位强胰，變成 2，然后再窮舉后兩位……
其實(shí)這就是回溯算法熟吏，我們高中無(wú)師自通就會(huì)用，或者有的同學(xué)直接畫(huà)出如下這棵回溯樹(shù)：
只要從根遍歷這棵樹(shù)牵寺，記錄路徑上的數(shù)字恩脂，其實(shí)就是所有的全排列。我們不妨把這棵樹(shù)稱(chēng)為回溯算法的「決策樹(shù)」俩块。
為啥說(shuō)這是決策樹(shù)呢，因?yàn)槟阍诿總€(gè)節(jié)點(diǎn)上其實(shí)都在做決策玉凯。比如說(shuō)你站在下圖的紅色節(jié)點(diǎn)上：
你現(xiàn)在就在做決策，可以選擇 1 那條樹(shù)枝漫仆，也可以選擇 3 那條樹(shù)枝捎拯。為啥只能在 1 和 3 之中選擇呢？因?yàn)?2 這個(gè)樹(shù)枝在你身后盲厌，這個(gè)選擇你之前做過(guò)了署照，而全排列是不允許重復(fù)使用數(shù)字的座菠。
現(xiàn)在可以解答開(kāi)頭的幾個(gè)名詞：[2] 就是「路徑」，記錄你已經(jīng)做過(guò)的選擇藤树；[1,3] 就是「選擇列表」，表示你當(dāng)前可以做出的選擇拓萌；「結(jié)束條件」就是遍歷到樹(shù)的底層岁钓，在這里就是選擇列表為空的時(shí)候。
如果明白了這幾個(gè)名詞微王，可以把「路徑」和「選擇」列表作為決策樹(shù)上每個(gè)節(jié)點(diǎn)的屬性屡限，比如下圖列出了幾個(gè)節(jié)點(diǎn)的屬性：
我們定義的 backtrack 函數(shù)其實(shí)就像一個(gè)指針，在這棵樹(shù)上游走炕倘，同時(shí)要正確維護(hù)每個(gè)節(jié)點(diǎn)的屬性钧大，每當(dāng)走到樹(shù)的底層，其「路徑」就是一個(gè)全排列罩旋。
再進(jìn)一步啊央，如何遍歷一棵樹(shù)？這個(gè)應(yīng)該不難吧涨醋」霞ⅲ回憶一下之前「學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的框架思維」寫(xiě)過(guò)，各種搜索問(wèn)題其實(shí)都是樹(shù)的遍歷問(wèn)題浴骂，而多叉樹(shù)的遍歷框架就是這樣：
void traverse(TreeNode root) {
for (TreeNode child : root.childern)
// 前序遍歷需要的操作
traverse(child);
// 后序遍歷需要的操作
}
而所謂的前序遍歷和后序遍歷乓土，他們只是兩個(gè)很有用的時(shí)間點(diǎn)，我給你畫(huà)張圖你就明白了：
前序遍歷的代碼在進(jìn)入某一個(gè)節(jié)點(diǎn)之前的那個(gè)時(shí)間點(diǎn)執(zhí)行溯警，后序遍歷代碼在離開(kāi)某個(gè)節(jié)點(diǎn)之后的那個(gè)時(shí)間點(diǎn)執(zhí)行趣苏。
回想我們剛才說(shuō)的，「路徑」和「選擇」是每個(gè)節(jié)點(diǎn)的屬性梯轻，函數(shù)在樹(shù)上游走要正確維護(hù)節(jié)點(diǎn)的屬性食磕，那么就要在這兩個(gè)特殊時(shí)間點(diǎn)搞點(diǎn)動(dòng)作：
現(xiàn)在，你是否理解了回溯算法的這段核心框架芬为？
for 選擇 in 選擇列表:
# 做選擇
將該選擇從選擇列表移除
路徑.add(選擇)
backtrack(路徑, 選擇列表)
# 撤銷(xiāo)選擇
路徑.remove(選擇)
將該選擇再加入選擇列表
我們只要在遞歸之前做出選擇媚朦，在遞歸之后撤銷(xiāo)剛才的選擇询张，就能正確得到每個(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)入下一層決策樹(shù)
backtrack(nums, track);
// 取消選擇
track.removeLast();
}
}
我們這里稍微做了些變通诀豁，沒(méi)有顯式記錄「選擇列表」舷胜，而是通過(guò) nums 和 track 推導(dǎo)出當(dāng)前的選擇列表：
至此，我們就通過(guò)全排列問(wèn)題詳解了回溯算法的底層原理展氓。當(dāng)然遇汞，這個(gè)算法解決全排列不是很高效簿废，應(yīng)為對(duì)鏈表使用 contains 方法需要 O(N) 的時(shí)間復(fù)雜度族檬。有更好的方法通過(guò)交換元素達(dá)到目的单料，但是難理解一些扫尖，這里就不寫(xiě)了换怖，有興趣可以自行搜索一下。
但是必須說(shuō)明的是悦污，不管怎么優(yōu)化切端，都符合回溯框架踏枣，而且時(shí)間復(fù)雜度都不可能低于 O(N!)，因?yàn)楦F舉整棵決策樹(shù)是無(wú)法避免的怠益。這也是回溯算法的一個(gè)特點(diǎn)蜻牢，不像動(dòng)態(tài)規(guī)劃存在重疊子問(wèn)題可以?xún)?yōu)化抢呆，回溯算法就是純暴力窮舉抱虐，復(fù)雜度一般都很高恳邀。
明白了全排列問(wèn)題，就可以直接套回溯算法框架了刷钢，下面簡(jiǎn)單看看 N 皇后問(wèn)題内地。
PS：我認(rèn)真寫(xiě)了 100 多篇原創(chuàng)赋除，手把手刷 200 道力扣題目举农，全部發(fā)布在 labuladong的算法小抄，持續(xù)更新秸妥。建議收藏粥惧，按照我的文章順序刷題突雪，掌握各種算法套路后投再入題海就如魚(yú)得水了涡贱。
二、N 皇后問(wèn)題
這個(gè)問(wèn)題很經(jīng)典了督函，簡(jiǎn)單解釋一下：給你一個(gè) N×N 的棋盤(pán)辰狡，讓你放置 N 個(gè)皇后宛篇，使得它們不能互相攻擊叫倍。
PS：皇后可以攻擊同一行段标、同一列炉奴、左上左下右上右下四個(gè)方向的任意單位瞻赶。
這個(gè)問(wèn)題本質(zhì)上跟全排列問(wèn)題差不多砸逊，決策樹(shù)的每一層表示棋盤(pán)上的每一行；每個(gè)節(jié)點(diǎn)可以做出的選擇是司倚，在該行的任意一列放置一個(gè)皇后皿伺。
直接套用框架:
vector<vector<string>> res;
/* 輸入棋盤(pán)邊長(zhǎng) n鸵鸥，返回所有合法的放置 */
vector<vector<string>> solveNQueens(int n) {
// '.' 表示空妒穴，'Q' 表示皇后讼油，初始化空棋盤(pán)呢簸。
vector<string> board(n, string(n, '.'));
backtrack(board, 0);
return res;
}
// 路徑：board 中小于 row 的那些行都已經(jīng)成功放置了皇后
// 選擇列表：第 row 行的所有列都是放置皇后的選擇
// 結(jié)束條件：row 超過(guò) board 的最后一行
void backtrack(vector<string>& board, int row) {
// 觸發(fā)結(jié)束條件
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';
// 進(jìn)入下一行決策
backtrack(board, row + 1);
// 撤銷(xiāo)選擇
board[row][col] = '.';
}
}
這部分主要代碼嘿架，其實(shí)跟全排列問(wèn)題差不多啸箫，isValid 函數(shù)的實(shí)現(xiàn)也很簡(jiǎn)單：
/* 是否可以在 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;
}
函數(shù) backtrack 依然像個(gè)在決策樹(shù)上游走的指針扎唾，通過(guò) row 和 col 就可以表示函數(shù)遍歷到的位置胸遇，通過(guò) isValid 函數(shù)可以將不符合條件的情況剪枝：
如果直接給你這么一大段解法代碼纸镊，可能是懵逼的逗威。但是現(xiàn)在明白了回溯算法的框架套路凯旭，還有啥難理解的呢罐呼？無(wú)非是改改做選擇的方式弄贿，排除不合法選擇的方式而已期奔，只要框架存于心危尿，你面對(duì)的只剩下小問(wèn)題了谊娇。
當(dāng) N = 8 時(shí)赠堵，就是八皇后問(wèn)題法褥，數(shù)學(xué)大佬高斯窮盡一生都沒(méi)有數(shù)清楚八皇后問(wèn)題到底有幾種可能的放置方法揍愁，但是我們的算法只需要一秒就可以算出來(lái)所有可能的結(jié)果杀饵。
不過(guò)真的不怪高斯切距。這個(gè)問(wèn)題的復(fù)雜度確實(shí)非常高，看看我們的決策樹(shù)话肖，雖然有 isValid 函數(shù)剪枝狼牺，但是最壞時(shí)間復(fù)雜度仍然是 O(N^(N+1))是钥，而且無(wú)法優(yōu)化虏冻。如果 N = 10 的時(shí)候弹囚，計(jì)算就已經(jīng)很耗時(shí)了蛮穿。
有的時(shí)候践磅，我們并不想得到所有合法的答案府适，只想要一個(gè)答案檐春，怎么辦呢疟暖？比如解數(shù)獨(dú)的算法朋贬，找所有解法復(fù)雜度太高锦募，只要找到一種解法就可以虐骑。
其實(shí)特別簡(jiǎn)單赎线，只要稍微修改一下回溯算法的代碼即可：
// 函數(shù)找到一個(gè)答案后就返回 true
bool backtrack(vector<string>& board, int row) {
// 觸發(fā)結(jié)束條件
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;
}
這樣修改后廷没，只要找到一個(gè)答案，for 循環(huán)的后續(xù)遞歸窮舉都會(huì)被阻斷垂寥。也許你可以在 N 皇后問(wèn)題的代碼框架上颠黎，稍加修改另锋，寫(xiě)一個(gè)解數(shù)獨(dú)的算法？
PS：我認(rèn)真寫(xiě)了 100 多篇原創(chuàng)狭归，手把手刷 200 道力扣題目夭坪，全部發(fā)布在 labuladong的算法小抄，持續(xù)更新过椎。建議收藏室梅，按照我的文章順序刷題亡鼠，掌握各種算法套路后投再入題海就如魚(yú)得水了讼撒。
三、最后總結(jié)
回溯算法就是個(gè)多叉樹(shù)的遍歷問(wèn)題，關(guān)鍵就是在前序遍歷和后序遍歷的位置做一些操作，算法框架如下：
def backtrack(...):
for 選擇 in 選擇列表:
做選擇
backtrack(...)
撤銷(xiāo)選擇
寫(xiě) backtrack 函數(shù)時(shí)，需要維護(hù)走過(guò)的「路徑」和當(dāng)前可以做的「選擇列表」窗宇，當(dāng)觸發(fā)「結(jié)束條件」時(shí)，將「路徑」記入結(jié)果集矗蕊。
其實(shí)想想看岖研，回溯算法和動(dòng)態(tài)規(guī)劃是不是有點(diǎn)像呢拓售？我們?cè)趧?dòng)態(tài)規(guī)劃系列文章中多次強(qiáng)調(diào)，動(dòng)態(tài)規(guī)劃的三個(gè)需要明確的點(diǎn)就是「狀態(tài)」「選擇」和「base case」玻侥，是不是就對(duì)應(yīng)著走過(guò)的「路徑」，當(dāng)前的「選擇列表」和「結(jié)束條件」波岛？
某種程度上說(shuō)，動(dòng)態(tài)規(guī)劃的暴力求解階段就是回溯算法仅父。只是有的問(wèn)題具有重疊子問(wèn)題性質(zhì)，可以用 dp table 或者備忘錄優(yōu)化燎字，將遞歸樹(shù)大幅剪枝，這就變成了動(dòng)態(tài)規(guī)劃领追。而今天的兩個(gè)問(wèn)題，都沒(méi)有重疊子問(wèn)題欧漱，也就是回溯算法問(wèn)題了窑邦，復(fù)雜度非常高是不可避免的瞧筛。
＿＿＿＿＿＿＿＿＿＿＿＿＿
我的 在線(xiàn)電子書(shū) 有 100 篇原創(chuàng)文章，手把手帶刷 200 道力扣題目衷恭，建議收藏！對(duì)應(yīng)的 GitHub 算法倉(cāng)庫(kù) 已經(jīng)獲得了 70k star，歡迎標(biāo)星魔慷！
