點擊上方藍字設為星標

下面開始今天的學習～

本文向大家介紹了回溯算法的基礎知識，以幫助大家更好地理解回溯算法。

回溯搜索算法簡介

維基百科中關于回溯算法的介紹是：

回溯算法(backtracking)是暴力搜索算法的一種。

這句話向我們揭示了回溯算法的用途：搜索，因此回溯算法也被稱為回溯搜索算法。

但它與 “二分查找” 、 “線性查找” 等 “查找問題” 不同的是，“搜索問題” 完成一件事情有可能多種方法，而每一種方法又有多個步驟，回溯算法就是在不斷嘗試，以得到待求問題的全部的解。

正是由于回溯算法具有“強大的”暴力搜索的能力，它被應用于一些游戲問題，例如：N 皇后、解數獨、祖瑪游戲、24 點游戲、走迷宮、生成迷宮。

許多復雜的、規模較大的問題都可以使用回溯搜索算法得到所有可行解，進而得到最優解，因此回溯算法有“通用解題方法”的美稱，回溯算法也是經典的人工智能的基礎算法。

本文只涉及回溯算法的基本知識，不會涉及到很高級的應用。

從全排列問題開始

我們從一個非常經典的問題開始講解回溯算法，這道題是「力扣」上第 46 號問題：“全排列”。

題目描述

給定一個沒有重復數字的序列，返回其所有可能的全排列。

示例:

輸入:?[1,?2,?3]
輸出:?[
??????[1,?2,?3],?
??????[1,?3,?2],?
??????[2,?1,?3],?
??????[2,?3,?1],?
??????[3,?1,?2],?
??????[3,?2,?1]
??????]

題目解析

這道題要求我們返回一個沒有重復數字的序列的所有可能的排列。

以題目示例為例，如果讓我們手動去寫，相信大家一定都會。

在動手嘗試寫出幾個全排列以后，會慢慢找到規律：

1、先下以 1 開頭的全排列，它們是：[1, 2, 3], [1, 3, 2]；
2、再寫下以 2 開頭的全排列，它們是：[2, 1, 3], [2, 3, 1]；
3、最后寫下以 3 開頭的全排列，它們是：[3, 1, 2], [3, 2, 1]。

這是一個非常典型的搜索問題，它的特點是：1、有若干個解；2、每一個解的求解過程可以分為若干個步驟，得到所有解是一個不斷嘗試的過程。

具體說，我們的思路是：按順序枚舉每一位可能出現的數字，之前已經出現的數字在接下來要選擇的數字中不能出現。

按照這種思路就能夠做到不重不漏，把所有的全排列都枚舉出來。

這樣的思路可以用一個樹形結構表示。

看到這里的朋友，不妨自己先嘗試畫一下“全排列”問題的樹形結構。

畫出樹形結構

使用編程的方法得到全排列，就是在這樣的一個樹形結構中進行搜索，從樹的根結點到葉子結點的路徑 path (下文也會用到的 path 就是此處的意思，就不再重復說明) 就是題目要求的一個全排列。

我們只需要執行一次深度優先遍歷(深度優先搜索)，就能夠得到所有的葉子結點。

相信提到深度優先搜索，不少朋友會想到樹和圖問題中另一個小伙伴的名字，它就是廣度優先遍歷(廣度優先搜索)。

那么廣度優先搜索是否可以應用在這道問題中呢？

既然是搜索，廣度優先搜索當然可以用于搜索。這個問題大家也不妨思考一下，全排列問題，既然用廣搜可以，為什么它是深搜的經典問題。

或許我們能想到一塊去。

理解為什么是深度優先遍歷，和回溯又有什么關系

下面我們解釋一下上面的樹形結構，請大家從深搜在這棵樹上走過的路徑來理解以下的幾點說明：

1、每一個結點表示了“全排列”問題求解的不同階段，這些階段通過變量的“不同的值”體現，這些變量的不同的值，稱之為“狀態”；

2、深度優先遍歷由于有“回頭”的過程，在“回頭”以后，狀態變量需要設置成為和先前一樣。在回到上一層結點的過程中，需要撤銷上一次選擇，這個操作也稱之為“狀態重置”，“狀態重置”就是“回溯”的本意；

3、使用深度優先遍歷編寫代碼，可以直接借助系統棧空間，為我們保存所需要的狀態變量。在編碼中需要注意：遍歷到相應的結點的時候，狀態變量的值是必須是正確的。此處我們來認識 path 變量作為狀態變量，它在深度優先遍歷中的變化：往下走一層的時候，path 變量在尾部追加一個數字，而往回走的時候，需要撤銷上一次的選擇，這一操作也是在 path 的尾部去掉一個數字，因此 path 變量是一個棧。

下面我們解釋如何編碼：

1、首先這棵樹除了葉子結點以外，每一個結點做的事情其實是一樣的，即在已經選了一些數的前提下，需要在剩下還沒有選擇的數中按照順序依次選擇一個數，這顯然是一個遞歸結構；

2、遞歸的終止條件是，數字的個數已經選夠了，因此我們需要一個變量來表示當前已經選了幾個數字，即當前遞歸到第幾層，我們把這個變量叫做 depth；

3、這些結點實際上表示了搜索全排列問題的不同階段，為了區分這些不同階段，我們就需要一些變量來記錄為了得到一個全排列，程序進行到哪一步，在這里我們需要兩個變量：

(1)已經選了哪些數，到葉子結點時候，這些已經選擇的數就構成了一個全排列，path 就是這樣的變量；
(2)一個布爾數組 used，初始化的時候都為 false，表示這些數還沒有被選擇，當我們選定一個數的時候，就將這個數組的相應位置設置為 true ，這樣在考慮下一個位置的時候，就能夠以 O(1) 的時間復雜度判斷這個數是否被選擇過，這是一種“以空間換時間”的思想。

這兩個變量稱之為“狀態變量”，它們?表示了我們在求解一個問題的時候所處的階段?。

4、在非葉子結點處，產生不同的分支，這一操作的語義是：在還未選擇的數中依次選擇一個元素作為下一個位置的元素，這顯然得通過一個循環實現。

5、另外，由于執行的深度優先遍歷，從較深層的結點返回到較淺層結點的時候，需要做“狀態重置”，即“回到過去”、“恢復現場”，我們舉一個例子：請大家看上面的樹形圖想象，代碼是如何從葉子結點 [1, 2, 3] 到葉子結點 [1, 3, 2] 的。深度優先遍歷是這樣執行的：

• 從 [1, 2, 3] 回到 [1, 2] 的時候，需要撤銷剛剛已經選擇的數 3；

• 由于在上一層只有一個數 3 能選擇，我們已經嘗試過了，因此程序回到再上一層，需要撤銷對 2 的選擇，好讓后面的程序知道，選擇 3 了以后還能夠選擇 2。

希望大家能通過在腦子里實際地像代碼一樣走一遍深度優先遍歷的過程，去理解代碼應該怎樣寫。或者直接看后面的代碼，然后去理解代碼為什么要這樣寫。事實上，我是先學習，然后再理解。

參考代碼 1

請讀者注意：這個代碼是 錯誤 的，有一個小坑，希望讀者能自己運行一下測試用例自己發現原因，然后再閱讀后面的內容。

import?java.util.ArrayList;
import?java.util.List;
public?class?Solution?{
????public?List>?permute(int[]?nums)?{//?首先是特判int?len?=?nums.length;//?使用一個動態數組保存所有可能的全排列
????????List>?res?=?new?ArrayList<>();if?(len?==?0)?{return?res;
????????}boolean[]?used?=?new?boolean[len];
????????List?path?=?new?ArrayList<>();
????????dfs(nums,?len,?0,?path,?used,?res);return?res;
????}private?void?dfs(int[]?nums,?int?len,?int?depth,
?????????????????????List?path,?boolean[]?used,
?????????????????????List>?res)?{if?(depth?==?len)?{
????????????res.add(path);return;
????????}for?(int?i?=?0;?i?????????????if?(!used[i])?{
????????????????path.add(nums[i]);
????????????????used[i]?=?true;
????????????????dfs(nums,?len,?depth?+?1,?path,?used,?res);//?注意：這里是狀態重置，是從深層結點回到淺層結點的過程，代碼在形式上和遞歸之前是對稱的
????????????????used[i]?=?false;
????????????????path.remove(depth);
????????????}
????????}
????}public?static?void?main(String[]?args)?{int[]?nums?=?{1,?2,?3};
????????Solution?solution?=?new?Solution();
????????List>?lists?=?solution.permute(nums);
????????System.out.println(lists);
????}
}

這段代碼在運行以后輸出如下：

[[],?[],?[],?[],?[],?[]]

得到了 6 個空列表的原因出現在遞歸終止條件這里：

if?(depth?==?len)?{
????res.add(path);
????return;
}

解釋：path 這個變量所指向的對象在遞歸的過程中只有一份。在深度優先遍歷完成以后，由于最后回到了根結點， path 這個變量為空列表。

依然是去想象深度優先遍歷的過程，從而理解為什么會到深搜會到原點以后為空列表，因為一開始就是空列表，深搜的過程轉了一圈，在不斷的選擇和回溯的過程以后，回到原點，依然是空列表。

這里需要說明的一點是：

在 Java 語言中，方法傳遞都是值傳遞。對象類型的變量在傳參的過程中，復制的都是變量的地址。這些地址被添加到 res 變量，但這些地址實際上指向的是同一塊內存的地址，因此我們會看到 6 個空的列表對象。解決這個問題的方法很簡單，在 res.add(path); 這里做一次拷貝即可。

修改的部分：

if?(depth?==?len)?{
????res.add(new?ArrayList<>(path));
????return;
}

此時再提交到「力扣」上就能得到一個 Accept 了。

復雜度分析

復雜度分析：(可以暫時跳過，或者永遠跳過，不是很重要，為了知識完整性寫在這里。)

由于公眾號對數學公式的排版不太友好，所以這里使用了截圖的形式：(

下面我們對這一版代碼做以下幾個說明：

1、如果在每一個非葉子結點分支的嘗試，我都創建新的變量表示狀態，那么

• 在回到上一層結點的時候不需要“回溯”；

• 在遞歸終止的時候也不需要做拷貝。

這樣的做法雖然可以得到解，但也會創建很多中間變量，這些中間變量很多時候是我們不需要的，會有一定空間和時間上的消耗。

為了驗證上面的說明，我們寫如下代碼進行實驗：

參考代碼 2

import?java.util.ArrayList;
import?java.util.List;

public?class?Solution?{
????public?List>?permute(int[]?nums)?{//?首先是特判int?len?=?nums.length;//?使用一個動態數組保存所有可能的全排列
????????List>?res?=?new?ArrayList<>();if?(len?==?0)?{return?res;
????????}boolean[]?used?=?new?boolean[len];
????????List?path?=?new?ArrayList<>();
????????dfs(nums,?len,?0,?path,?used,?res);return?res;
????}private?void?dfs(int[]?nums,?int?len,?int?depth,
?????????????????????List?path,?boolean[]?used,
?????????????????????List>?res)?{if?(depth?==?len)?{//?3、不用拷貝，因為每一層傳遞下來的?path?變量都是新建的
????????????res.add(path);return;
????????}for?(int?i?=?0;?i?????????????if?(!used[i])?{//?1、每一次嘗試都創建新的變量表示當前的"狀態"
????????????????List?newPath?=?new?ArrayList<>(path);
????????????????newPath.add(nums[i]);boolean[]?newUsed?=?new?boolean[len];
????????????????System.arraycopy(used,?0,?newUsed,?0,?len);
????????????????newUsed[i]?=?true;
????????????????dfs(nums,?len,?depth?+?1,?newPath,?newUsed,?res);//?2、無需回溯
????????????}
????????}
????}
}

這就好比我們在實驗室里做“對比實驗”，只有每一個步驟的嘗試都都使用同樣的材料，才有可能保證“對比實驗”結果的有效性。
為此我們有兩種做法：

• 每做完一種嘗試，都把實驗材料恢復成做上一個實驗之前的樣子，只有這樣做出的對比才有意義；

• 每一次嘗試都使用同樣的新的材料做實驗。

在生活中做實驗對材料有破壞性，這個過程通常不可逆。

而在計算機的世界里，“恢復現場”和“回到過去”是相對容易的。

在一些字符串的“回溯”問題中，有時不需要回溯的原因是這樣的：字符串變量在拼接的過程中會產生新的對象(針對 Java 和 Python 語言，其它語言我并不清楚)。

如果你使用 Python 語言，會知道有這樣一種語法：[1, 2, 3] + [4] 創建了一個新的列表對象，請看“參考代碼 3”。

參考代碼 3

from?typing?import?List
class?Solution:
????def?permute(self,?nums:?List[int])?->?List[List[int]]:
????????def?dfs(nums,?size,?depth,?path,?state,?res):
????????????if?depth?==?size:
????????????????res.append(path)
????????????????return

????????????for?i?in?range(size):
????????????????if?((state?>>?i)?&?1)?==?0:
????????????????????dfs(nums,?size,?depth?+?1,?path?+?[nums[i]],?state?^?(1?<
????????size?=?len(nums)
????????if?size?==?0:
????????????return?[]

????????state?=?0
????????res?=?[]
????????dfs(nums,?size,?0,?[],?state,?res)
????????return?res

說明：這里的整數 state 代替了布爾數組 used 的作用。布爾數組 used 在這題里的作用是判斷某個位置上的元素是否已經使用過。

它有兩種等價的替換方式：

(1)位掩碼，即使用一個整數表示布爾數組。此時可以將空間復雜度降到 O(1)(不包括 path 變量和 res 變量和遞歸棧空間消耗)，本 Python 代碼正好展示了這樣的寫法；

(2)哈希表，代碼留給讀者完成。

2、(只與 Java 語言相關)ArrayList 是 Java 中的動態數組，Java 建議我們如果一開始就知道這個集合里需要保存元素的大小，可以在初始化的時候直接傳入。

在這里，由于我們很清楚全排列的總是就是候選數組長度的階乘值，因此在 res 變量初始化的時候，最好傳入 len 的階乘，讓 ArrayList 在代碼執行的過程中不發生擴容行為。同理，在 path 變量初始化的時候，最好傳入 len，事實這個路徑變量最長也就到 len。

3、path 變量我們發現只是對它的末尾位置進行增加和刪除的操作，顯然它是一個棧，因此，使用棧語義會更清晰。

(只與 Java 語言相關)但同時 Stack 這個類的文檔告訴我們，由于一些設計上的問題，建議我們使用：

Deque?stack?=?new?ArrayDeque();

這一點讓我們覺得比較左右為難：Deque 是雙端隊列，它提供了更靈活的接口，但同時破壞了語義，一不小心，如果用錯了接口，就會導致程序錯誤。我采用的做法是接受官方的建議，并且(1)在程序變量命名和使用的接口時讓語義清晰；(2)加上必要的注釋；(3)加強測試。

這里 path 需要表示它是從根結點到葉子結點的路徑，我認為這個語義更重要，因此不改名為 stack。而在末尾添加元素和刪除元素的時候，分別使用 addLast() 和 removeLast() 方法這兩個最直接的方法名強調只在 path 變量的末尾操作。

到此為止，回溯搜索算法的基本思想，除了“剪枝”，我們已經介紹完了，下面做一個簡單的總結。

總結

回溯算法就是在一個樹形問題上做一次深度優先遍歷，以達到搜索所有可能的解的效果。

為什么使用深度優先遍歷？

• 首先是正確性，只有遍歷狀態空間，才能得到所有符合條件的解；

• 在深度優先遍歷的時候，不同狀態之間的切換很容易，可以再看一下上面有很多箭頭的那張圖，每兩個狀態之間的差別只有 1 處，因此回退非常方便，這樣全局就使用一份狀態變量完成搜索；

• 如果每一個狀態都去創建新的變量，時間復雜度是 O(N)，并且也有空間的消耗。

• 搜索問題的狀態空間一般很大，在候選數比較多的時候，在非葉子結點上創建新的狀態變量的性能消耗就很嚴重；

• 就本題而言，只需要葉子結點的那個狀態，在葉子結點執行拷貝，時間復雜度是 ?O(N)。路徑變量在深度優先遍歷的時候，結點之間的轉換只需要 ?O(1)。

為什么不使用廣度優先遍歷？

• 如果使用廣度優先遍歷，從淺層轉到深層(請讀者想象廣搜的過程)，狀態的變化就很大，此時我們不得不在每一個狀態都新建變量去保存它，上面已經分析過了，從性能來說是不劃算的；

• 從編寫代碼的角度上來說，如果使用廣度優先遍歷就得使用隊列，然后編寫結點類。而使用深度優先遍歷，我們可以直接使用了系統棧，系統棧幫助我們保存了每一個結點的狀態信息。于是我們不用編寫結點類，不必手動編寫棧完成深度優先遍歷。

這道題用廣度優先遍歷寫是完全可以的，我嘗試過，代碼寫出來非常不美觀。

感興趣的朋友也可以嘗試寫一下，嘗試寫廣搜的目的是更好地體會為什么“深搜”能成為強大的“回溯搜索算法”，而廣搜不是。

認識“剪枝”

由于回溯算法的時間復雜度很高，因此，在遍歷的時候，如果能夠提前知道這一條分支不能搜索到滿意的結果，這一分支就可以跳過，這一步操作就是在一棵樹上剪去一個枝葉，被人們很形象地稱之為剪枝。

回溯算法會大量應用“剪枝”技巧達到以加快搜索速度。這里有幾點提示：

1、有時，需要做一些預處理工作(例如排序)才能達到剪枝的目的。雖然預處理工作雖然也消耗時間，但和剪枝能夠節約的時間相比是微不足道的。因此，能預處理的話，就盡量預處理；

2、正是因為回溯問題本身時間復雜度就很高，所以能用空間換時間就盡量使用空間。

如果大家玩得轉“剪枝”，或許在開篇列出的一些簡單的游戲問題就不在話下了，感興趣的朋友不妨挑戰一下。關于“剪枝”的技巧，以后有機會，我再和大家做一次分享。

練習

下面提供一些我做過的“回溯”算法的問題，都是特別基礎的使用回溯算法解決的問題，以便大家學習和理解“回溯算法”。以下提供一個經驗：

做回溯搜索問題?第 1 步都是先畫圖，畫圖是非常重要的，只有畫圖才能幫助我們想清楚遞歸結構，看清楚、想清楚如何剪枝。

具體的做法是：就拿題目中的示例，想一想人手動操作是怎么做的，一般這樣下來，這棵遞歸樹都不難畫出。

在畫圖的過程中需要思考清楚的問題有：

1、分支如何產生，即：每一步有哪些選擇；

2、題目需要的解在哪里？是在葉子結點、還是在非葉子結點、還是在從跟結點到葉子結點的路徑？

3、哪些搜索是會產生不需要的解的，這里要特別清楚深搜是怎么運行的，在深搜的過程中，狀態變量發生了什么變化。例如：產生重復是什么原因，如果在淺層就知道這個分支不能產生需要的結果，應該提前剪枝，剪枝的條件是什么，代碼怎么寫？

五分鐘學算法：思維導圖

回溯算法基礎問題列表

題目提示

47. 全排列 II	思考一下，為什么造成了重復，如何在搜索之前就判斷這一支會產生重復，從而“剪枝”。
17 .電話號碼的字母組合	字符串問題，沒有顯式回溯的過程
22. 括號生成	字符串問題，沒有顯式回溯的過程。這道題廣度優先遍歷也很好寫，可以通過這個問題理解一下為什么回溯算法都是深度優先遍歷，并且都用遞歸來寫。
39. 組合總和	使用題目給的示例，畫圖分析。
40. 組合總和 II
51. N皇后	其實就是全排列問題，注意設計清楚狀態變量。
60. 第k個排列	利用了剪枝的思想，剪去了大量枝葉，直接來到需要的葉子結點。
77. 組合	組合問題按順序找，就不會重復。并且舉一個中等規模的例子，找到如何剪枝，這道題思想不難，難在編碼。
78. 子集	為數不多的，解不在葉子結點上的回溯搜索問題。解法比較多，注意對比。
90. 子集 II	剪枝技巧同 47 題、39 題、40 題。
93. 復原IP地址
784. 字母大小寫全排列

END

---

●?答應我，別再if/else走天下了可以嗎

●?如何利用寒假的時間來準備2020年的藍橋杯?

●?給大家推薦一款軟件

● 關于計算機讀研的小建議

原創不易，點“在看”你懂得?

總結

以上是生活随笔為你收集整理的c语言全排列算法_一文学会回溯搜索算法解题技巧的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。