一文學會「回溯搜索演算法」解題技巧

• 2020 年 2 月 20 日
• 筆記

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

回溯搜索演算法簡介

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

回溯演算法（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<List<Integer>> permute(int[] nums) {          // 首先是特判          int len = nums.length;          // 使用一個動態數組保存所有可能的全排列          List<List<Integer>> res = new ArrayList<>();          if (len == 0) {              return res;          }          boolean[] used = new boolean[len];          List<Integer> path = new ArrayList<>();            dfs(nums, len, 0, path, used, res);          return res;      }        private void dfs(int[] nums, int len, int depth,                       List<Integer> path, boolean[] used,                       List<List<Integer>> res) {          if (depth == len) {              res.add(path);              return;          }            for (int i = 0; i < len; 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<List<Integer>> 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<List<Integer>> permute(int[] nums) {          // 首先是特判          int len = nums.length;          // 使用一個動態數組保存所有可能的全排列          List<List<Integer>> res = new ArrayList<>();            if (len == 0) {              return res;          }            boolean[] used = new boolean[len];          List<Integer> path = new ArrayList<>();            dfs(nums, len, 0, path, used, res);          return res;      }        private void dfs(int[] nums, int len, int depth,                       List<Integer> path, boolean[] used,                       List<List<Integer>> res) {          if (depth == len) {              // 3、不用拷貝，因為每一層傳遞下來的 path 變數都是新建的              res.add(path);              return;          }            for (int i = 0; i < len; i++) {              if (!used[i]) {                  // 1、每一次嘗試都創建新的變數表示當前的"狀態"                  List<Integer> 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 << i), res)            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<Integer> stack = new ArrayDeque<Integer>();  

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

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

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

總結

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

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

• 首先是正確性，只有遍歷狀態空間，才能得到所有符合條件的解；
• 在深度優先遍歷的時候，不同狀態之間的切換很容易，可以再看一下上面有很多箭頭的那張圖，每兩個狀態之間的差別只有 1 處，因此回退非常方便，這樣全局就使用一份狀態變數完成搜索；
• 如果每一個狀態都去創建新的變數，時間複雜度是 O(N)，並且也有空間的消耗。
• 搜索問題的狀態空間一般很大，在候選數比較多的時候，在非葉子結點上創建新的狀態變數的性能消耗就很嚴重；
• 就本題而言，只需要葉子結點的那個狀態，在葉子結點執行拷貝，時間複雜度是 O(N)。路徑變數在深度優先遍歷的時候，結點之間的轉換隻需要 O(1)。

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

• 如果使用廣度優先遍歷，從淺層轉到深層（請讀者想像廣搜的過程），狀態的變化就很大，此時我們不得不在每一個狀態都新建變數去保存它，上面已經分析過了，從性能來說是不划算的；
• 從編寫程式碼的角度上來說，如果使用廣度優先遍歷就得使用隊列，然後編寫結點類。而使用深度優先遍歷，我們可以直接使用了系統棧，系統棧幫助我們保存了每一個結點的狀態資訊。於是我們不用編寫結點類，不必手動編寫棧完成深度優先遍歷。

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

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

認識「剪枝」

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

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

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

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

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

練習

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

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

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

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

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

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

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

五分鐘學演算法：思維導圖

回溯演算法基礎問題列表