「回溯算法」專(zhuān)題介紹

第 1 節(jié)：從全排列問(wèn)題開(kāi)始理解回溯搜索算法

引言

大家好，今天要和大家分享的主題是“回溯算法”。

“回溯算法”的全稱(chēng)是“回溯搜索算法”，“搜索”這個(gè)詞揭示了“回溯”算法的應(yīng)用：“搜索”。

首先我們來(lái)理解一下“搜索”這個(gè)詞：

這里的“搜索”類(lèi)似我們學(xué)習(xí)過(guò)的“查找”，類(lèi)似于“線(xiàn)性查找”、“二分查找”，我們是為了查找某個(gè)元素而使用查找算法，而搜索算法更強(qiáng)大了，“回溯搜索算法”可以幫助我們查找到符合條件的一系列的解，這里“搜索”的含義完全可以理解成我們?nèi)粘Ｊ褂玫摹八阉饕妗崩锏摹八阉鳌薄?/p>

搜索引擎：在一個(gè)龐大的空間（互聯(lián)網(wǎng)世界）里搜索我們需要的內(nèi)容。

回溯搜索：在一個(gè)樹(shù)形問(wèn)題里搜索符合條件的解的集合。

也就是使用搜索算法，能夠幫助我們找到的問(wèn)題的答案不止一個(gè)，有多少個(gè)答案，搜索算法就會(huì)返回給你多少個(gè)答案。

例 1：「力扣」第 46 題：全排列

我們先來(lái)看一個(gè)最基本的使用回溯算法解決的問(wèn)題，這道題是「力扣」上第 46 號(hào)問(wèn)題：“全排列”。

給定一個(gè)沒(méi)有重復(fù)數(shù)字的序列，返回其所有可能的全排列。
示例:
輸入: [1, 2, 3]
輸出: [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]

這道題要求我們返回一個(gè)沒(méi)有重復(fù)數(shù)字的序列的所有可能的排列。以題目示例為例，如果讓我們手寫(xiě)，相信大家一定都會(huì)。在動(dòng)手嘗試寫(xiě)出幾個(gè)全排列以后，會(huì)慢慢找到規(guī)律，我們就以 [1, 2, 3] 為例，手寫(xiě)得到全排列的過(guò)程是這樣的：

• 先下以 1 開(kāi)頭的全排列，它們是：[1, 2, 3], [1, 3, 2]；
• 再寫(xiě)下以 2 開(kāi)頭的全排列，它們是：[2, 1, 3], [2, 3, 1]；
• 最后寫(xiě)下以 3 開(kāi)頭的全排列，它們是：[3, 1, 2], [3, 2, 1]。

具體來(lái)說(shuō)，這種做法思路是：

• 按順序枚舉每一個(gè)位置可能出現(xiàn)的數(shù)字；
• 之前已經(jīng)出現(xiàn)的數(shù)字在接下來(lái)要選擇的數(shù)字中不能出現(xiàn)。

按照這種思路就能夠做到不重不漏，把所有的排列都枚舉出來(lái)。
這樣的思路可以用一個(gè)樹(shù)形結(jié)構(gòu)表示?？吹竭@里的朋友，不妨自己先嘗試畫(huà)出“全排列”問(wèn)題的樹(shù)形結(jié)構(gòu)。

全排列問(wèn)題的樹(shù)形結(jié)構(gòu)

下面我就為大家展示一下，這個(gè)問(wèn)題畫(huà)成樹(shù)形結(jié)構(gòu)是怎樣的。我們的做法是一個(gè)位置一個(gè)位置去嘗試，窮舉所有的可能性。

以 [1, 2, 3] 為例（說(shuō)明得到全排列的樹(shù)形結(jié)構(gòu)）。

• 一開(kāi)始，排列為空列表；
• 第 1 個(gè)位置可能出現(xiàn)的數(shù)值為 1、2、3、
• 第 2 個(gè)位置，我們看 1 這個(gè)分支，由于 1 已經(jīng)使用過(guò)，那么第 2 個(gè)位置可能出現(xiàn)的數(shù)字只能是 2 和 3，同理不難寫(xiě)出 2 這個(gè)分支和 3 這個(gè)分支；
• 第 3 個(gè)位置，我們看 1, 2 這個(gè)分支，由于只有 1、2 都被選了，只能選擇 3，于是得到一個(gè)排列 [1, 2, 3]，同理，這一條路徑走到最后，能選擇的數(shù)字只有 2，得到了另一個(gè)排列 [1, 3, 2]，依次類(lèi)推，得到排列 [2, 1, 3]、[2, 3, 1] 、[3, 1, 2] 、[3, 2, 1]。在這樣一個(gè)樹(shù)形結(jié)構(gòu)中，我們畫(huà)在葉子結(jié)點(diǎn)的所有排列就是 [1, 2, 3] 的全排列。

方法知道了，下面我們考慮如何寫(xiě)代碼，事實(shí)上，我展示這個(gè)動(dòng)畫(huà)的過(guò)程就可以作為一種編碼的方法，它是這棵樹(shù)的廣度優(yōu)先遍歷的過(guò)程，感興趣的朋友不妨嘗試一下廣度優(yōu)先遍歷應(yīng)該怎樣寫(xiě)，大家真正去寫(xiě)一下就會(huì)發(fā)現(xiàn)廣度優(yōu)先遍歷的寫(xiě)法并不好寫(xiě)。

既然我們說(shuō)到了“遍歷”，與“廣度優(yōu)先遍歷”一起會(huì)在我們腦海里出現(xiàn)的名詞就是“深度優(yōu)先遍歷”，我要為大家介紹的“回溯搜索算法”就是在這棵多叉樹(shù)上做“深度優(yōu)先遍歷”。

我們先把深度優(yōu)先遍歷的路徑畫(huà)在這棵樹(shù)上是這樣的，我們?cè)倬唧w跟蹤一下深度優(yōu)先遍歷的遍歷過(guò)程。

image-20200120041102590

• 從一個(gè)空列表開(kāi)始，先選擇 1，然后因?yàn)?1 已經(jīng)選擇了，按順序應(yīng)該選擇 2 ，還沒(méi)完呢，還有一個(gè)數(shù) 3，此時(shí)我們發(fā)現(xiàn)沒(méi)有數(shù)字可選了，即得到了一個(gè)排列；
• 為了得到全部的排列，深度優(yōu)先遍歷有一個(gè)回退的過(guò)程，最后一步我們選擇的是 3，在回退的時(shí)候，需要撤銷(xiāo)對(duì) 3 的選擇，回到 [1, 2] ，由于在這個(gè)階段，選擇 3 已經(jīng)被我們考慮了，因此繼續(xù)回退，撤銷(xiāo)對(duì) 2 的選擇，回退到 [1]，在這個(gè)階段有 2 個(gè)選擇，可以選擇 2，也可以選擇 3，2 已經(jīng)走過(guò)了，接下來(lái)選擇 3，接下來(lái)可以選擇的只有 2，于是又得到一個(gè)排列 [1, 3, 2]，為了得到其他排列，我們撤銷(xiāo)對(duì) 2 的選擇，撤銷(xiāo)對(duì) 3 的選擇；
• 在 1 這個(gè)結(jié)點(diǎn)，可以選擇的第 2 個(gè)位置的數(shù)值 2、3 我們已經(jīng)走過(guò)了，也就是我們得到了以 1 開(kāi)頭的排列，為了得到以 2、3 開(kāi)頭的全排列，我們依然是像剛剛做過(guò)的操作一樣，在回退的時(shí)候，撤銷(xiāo)對(duì) 1 的選擇，回到空結(jié)點(diǎn)；
• 接下來(lái)的步驟是類(lèi)似的，我直接展示給大家看。下面我們總結(jié)一下深度優(yōu)先遍歷是如何在這棵樹(shù)上完成遍歷操作的：

第 1 點(diǎn)：首先介紹一個(gè)概念：狀態(tài)。

每一個(gè)結(jié)點(diǎn)表示了求解“全排列”問(wèn)題的不同階段，這些階段通過(guò)變量的“不同的值”體現(xiàn)，這些變量的不同的值，稱(chēng)之為“狀態(tài)”；

例如 [3] 這個(gè)結(jié)點(diǎn)，表示的就是我們已經(jīng)確定了一個(gè)排列的第一個(gè)位置的元素是 [3]，這是一個(gè)階段，還沒(méi)完呢，在這個(gè)階段下，我們還要去找后面兩個(gè)位置可能出現(xiàn)的元素有哪一些情況。

第 2 點(diǎn)：深度優(yōu)先遍歷由于有“回頭”的過(guò)程，在“回頭”以后，狀態(tài)變量需要設(shè)置成為和之前剛來(lái)到這個(gè)結(jié)點(diǎn)的時(shí)候一樣。具體的表現(xiàn)就是：在回到上一層結(jié)點(diǎn)的時(shí)候，需要撤銷(xiāo)上一次選擇，這個(gè)操作也稱(chēng)之為“狀態(tài)重置”，這里“狀態(tài)重置”就是“回溯算法”里“回溯”的本意；

• 正因?yàn)榛氐搅酥暗牡臓顟B(tài)，才可以開(kāi)始下一個(gè)選擇的嘗試，大家可以從反面想一下，如果不重置的話(huà)，會(huì)發(fā)生怎樣的情況。

下面我們解釋如何編碼：

1、首先這棵樹(shù)除了葉子結(jié)點(diǎn)以外，每一個(gè)結(jié)點(diǎn)做的事情其實(shí)是一樣的，即在已經(jīng)選了一些數(shù)的前提下，需要在剩下還沒(méi)有選擇的數(shù)中按照順序依次選擇一個(gè)數(shù)，這顯然是一個(gè)遞歸結(jié)構(gòu)；

2、是遞歸，萬(wàn)年不變的前提就是要考慮遞歸終止條件。

遞歸的終止條件是：數(shù)字的個(gè)數(shù)已經(jīng)選夠了。因此我們需要一個(gè)變量來(lái)表示當(dāng)前已經(jīng)選了幾個(gè)數(shù)字，這個(gè)變量等價(jià)的含義是在這棵樹(shù)上當(dāng)前遍歷到了這棵樹(shù)的第幾層，我們把這個(gè)變量叫做 depth；

當(dāng) depth == len （len 是序列中數(shù)字的個(gè)數(shù)）的時(shí)候，遞歸終止。

3、剛剛我們說(shuō)了，這些結(jié)點(diǎn)表示了深度優(yōu)先遍歷的不同階段，為了區(qū)分這些不同階段，我們就需要一些變量來(lái)記錄為了得到一個(gè)全排列，程序進(jìn)行到哪一步，在這里我們?cè)O(shè)計(jì)兩個(gè)變量：

（1）已經(jīng)選了哪些數(shù) path

由于排列是講究順序的，已經(jīng)選擇的數(shù)我們把它放進(jìn)一個(gè)列表里，這個(gè)列表里的數(shù)字就是從根結(jié)點(diǎn)到某個(gè)中間結(jié)點(diǎn)或者葉子結(jié)點(diǎn)的一個(gè)路徑，我們把這個(gè)列表命名為 path。

注意到，在每一個(gè)結(jié)點(diǎn)，我們要判斷有哪些數(shù)字還可以被選擇，我們當(dāng)然可以通過(guò)看 path 這個(gè)變量知道已經(jīng)被選擇的數(shù)，但是每做一次判斷，就需要把 path 遍歷一次。

（2）布爾數(shù)組 used

一個(gè)經(jīng)典的做法就是，我們?cè)僭O(shè)置一個(gè)布爾數(shù)組，表示當(dāng)前考慮的數(shù)字是否在之前已經(jīng)選擇過(guò)，即它是否在當(dāng)前的 path 變量里，這樣我們就可以以 的時(shí)間復(fù)雜度完成這個(gè)判斷。

我把這個(gè)布爾數(shù)組命名為 used，初始化的時(shí)候都為 false，表示這些數(shù)還沒(méi)有被選擇，當(dāng)我們選定一個(gè)數(shù)的時(shí)候，就將這個(gè)數(shù)組的相應(yīng)位置設(shè)置為 true。

設(shè)置布爾數(shù)組，是一種典型的“以空間換時(shí)間”的思想。

path 、depth、used 這三個(gè)變量稱(chēng)之為“狀態(tài)變量”，它們表示了我們?cè)谇蠼馊帕袉?wèn)題的時(shí)候所處的階段。

4、在非葉子結(jié)點(diǎn)處，產(chǎn)生不同的分支，這一操作的語(yǔ)義是：在還未選擇的數(shù)中依次選擇一個(gè)元素作為下一個(gè)位置的元素，這顯然需要通過(guò)一個(gè)循環(huán)實(shí)現(xiàn)。

接下來(lái)，我們看一下代碼怎么寫(xiě)：

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;
        }

        List<Integer> path = new ArrayList<>();
        boolean[] used = new boolean[len];
        dfs(nums, len, 0, path, used, res);
        return res;
    }

    /**
     * @param nums  候選數(shù)字列表
     * @param len   列表長(zhǎng)度，可以直接從 nums.length 里獲取，因?yàn)樾枰褂玫拇螖?shù)很多，設(shè)計(jì)這個(gè)冗余的變量
     * @param depth 已經(jīng)選了幾個(gè)數(shù)字
     * @param path  已經(jīng)選擇的數(shù)字列表
     * @param used  快速判斷某個(gè)數(shù)是否已經(jīng)被選擇
     * @param res   記錄結(jié)果集的列表
     */
    private void dfs(int[] nums, int len, int depth, List<Integer> path, boolean[] used, List<List<Integer>> res) {
        if (depth == len) {
            // 這里留坑
            res.add(new ArrayList<>(path));
            return;
        }

        for (int i = 0; i < len; i++) {
            if (used[i]) {
                continue;
            }

            path.add(nums[i]);
            used[i] = true;
            dfs(nums, len, depth + 1, path, used, res);
            // 這個(gè)位置是深度優(yōu)先遍歷回退的步驟，我們需要在這里對(duì)狀態(tài)遍歷做重置的操作
            path.remove(depth);
            used[i] = false;
        }
    }
}

這段代碼在運(yùn)行以后輸出如下：

[[], [], [], [], [], []]

得到了 6 個(gè)空列表的原因出現(xiàn)在遞歸終止條件這里：

Java 代碼：

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

解釋?zhuān)?code>path 這個(gè)變量所指向的對(duì)象在遞歸的過(guò)程中只有一份。在深度優(yōu)先遍歷完成以后，由于最后回到了根結(jié)點(diǎn)， path 這個(gè)變量為空列表。

依然是去想象深度優(yōu)先遍歷的過(guò)程，從而理解為什么會(huì)到深搜會(huì)到原點(diǎn)以后為空列表，因?yàn)橐婚_(kāi)始就是空列表，深搜的過(guò)程轉(zhuǎn)了一圈，在不斷的選擇和回溯的過(guò)程以后，回到原點(diǎn)，依然是空列表。

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

修改的部分：

Java 代碼：

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

此時(shí)再提交到「力扣」上就能得到一個(gè) Accept 了。

（復(fù)雜度分析最后說(shuō)。）

剛學(xué)習(xí)回溯算法的朋友，可能對(duì)這里為什么需要回溯并不能很好地理解。為此我再花一點(diǎn)時(shí)間深入和大家探討一下全排列問(wèn)題的回溯算法。

幾點(diǎn)說(shuō)明

首先是可不可以不“回溯”呢，我們?cè)趧倓倻y(cè)試的過(guò)程中也發(fā)現(xiàn)，new ArrayList<>(path) 這段代碼顯得不是那么自然，很容易被我們忽略。下面我們分析一下其中的原因，其實(shí)我們剛剛也說(shuō)了，是由于 path 這個(gè)變量所指向的對(duì)象在遞歸的過(guò)程中只有一份。一個(gè)大膽的想法是：

1、如果在每一個(gè)非葉子結(jié)點(diǎn)分支的嘗試，都創(chuàng)建新的變量表示狀態(tài)，那么

• 在回到上一層結(jié)點(diǎn)的時(shí)候不需要“回溯”（也就是不需要“狀態(tài)重置”）；
• 在遞歸終止的時(shí)候也不需要做拷貝。

為了驗(yàn)證這種說(shuō)法，我們寫(xiě)如下代碼進(jìn)行實(shí)驗(yàn)：

Java 代碼：

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;
        }

        List<Integer> path = new ArrayList<>();
        boolean[] used = new boolean[len];
        dfs(nums, len, 0, path, used, res);
        return res;
    }

    /**
     * @param nums  候選數(shù)字列表
     * @param len   列表長(zhǎng)度，可以直接從 nums.length 里獲取，因?yàn)樾枰褂玫拇螖?shù)很多，設(shè)計(jì)這個(gè)冗余的變量
     * @param depth 已經(jīng)選了幾個(gè)數(shù)字
     * @param path  已經(jīng)選擇的數(shù)字列表
     * @param used  快速判斷某個(gè)數(shù)是否已經(jīng)被選擇
     * @param res   記錄結(jié)果集的列表
     */
    private void dfs(int[] nums, int len, int depth, List<Integer> path, boolean[] used, List<List<Integer>> res) {
        if (depth == len) {
            // 無(wú)需拷貝
            // res.add(new ArrayList<>(path));
            res.add(path);
            return;
        }

        for (int i = 0; i < len; i++) {
            if (used[i]) {
                continue;
            }

            // 在每一個(gè)結(jié)點(diǎn)創(chuàng)建新變量有一定性能消耗
            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);
            // 無(wú)回溯過(guò)程
        }
    }
}

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

這就好比我們?cè)趯?shí)驗(yàn)室里做“對(duì)比實(shí)驗(yàn)”，只有每一個(gè)步驟的嘗試都都使用同樣的材料，才有可能保證“對(duì)比實(shí)驗(yàn)”結(jié)果的有效性。
為此我們有兩種做法：

• 每做完一種嘗試，都把實(shí)驗(yàn)材料恢復(fù)成做上一個(gè)實(shí)驗(yàn)之前的樣子，只有這樣做出的對(duì)比才有意義；
• 每一次嘗試都使用同樣的新的材料做實(shí)驗(yàn)。

在生活中做實(shí)驗(yàn)對(duì)材料有破壞性，這個(gè)過(guò)程通常不可逆。而在計(jì)算機(jī)的世界里，“恢復(fù)現(xiàn)場(chǎng)”和“回到過(guò)去”是相對(duì)容易的。

在一些字符串的“回溯”問(wèn)題中，有時(shí)不需要回溯的原因是這樣的：字符串變量在拼接的過(guò)程中會(huì)產(chǎn)生新的對(duì)象（針對(duì) Java 和 Python 語(yǔ)言，其它語(yǔ)言我并不清楚）。

如果你使用 Python 語(yǔ)言，會(huì)知道有這樣一種語(yǔ)法：[1, 2, 3] + [4] 創(chuàng)建了一個(gè)新的列表對(duì)象，請(qǐng)看“參考代碼 3”。

參考代碼 3：

Python 代碼：

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

說(shuō)明：這里的整數(shù) state 代替了布爾數(shù)組 used 的作用。布爾數(shù)組 used 在這題里的作用是判斷某個(gè)位置上的元素是否已經(jīng)使用過(guò)。它有兩種等價(jià)的替換方式：

（1）位掩碼，即使用一個(gè)整數(shù)表示布爾數(shù)組。此時(shí)可以將空間復(fù)雜度降到 （不包括 path 變量和 res 變量和遞歸?？臻g消耗），本 Python 代碼正好展示了這樣的寫(xiě)法；

（2）哈希表。

代碼留給大家完成。

2、path 變量我們發(fā)現(xiàn)只是對(duì)它的末尾位置進(jìn)行增加和刪除的操作，顯然它是一個(gè)棧，因此，使用棧語(yǔ)義會(huì)更清晰。

（只與 Java 語(yǔ)言相關(guān)）但同時(shí) Stack 這個(gè)類(lèi)的文檔告訴我們，由于一些設(shè)計(jì)上的問(wèn)題，建議我們使用：

Deque<Integer> stack = new ArrayDeque<Integer>();

這一點(diǎn)讓我們覺(jué)得比較左右為難：Deque 是雙端隊(duì)列，它提供了更靈活的接口，但同時(shí)破壞了語(yǔ)義，一不小心，如果用錯(cuò)了接口，就會(huì)導(dǎo)致程序錯(cuò)誤。

在「力扣」這個(gè)網(wǎng)站上一起刷題的朋友給我的建議就是：是接受官方的建議，并且（1）在程序變量命名和使用的接口時(shí)讓語(yǔ)義清晰；（2）加上必要的注釋?zhuān)唬?）加強(qiáng)測(cè)試。

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

3、最后這一點(diǎn)只和 Java 語(yǔ)法相關(guān)。

（只與 Java 語(yǔ)言相關(guān)）ArrayList 是 Java 中的動(dòng)態(tài)數(shù)組，Java 建議我們?nèi)绻婚_(kāi)始就知道這個(gè)集合里需要保存元素的大小，可以在初始化的時(shí)候直接傳入。

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

代碼留給大家完成。

到此為止，回溯搜索算法的基本思想。相信大家已經(jīng)認(rèn)識(shí)到了，“回溯算法 = 深度優(yōu)先遍歷 + 狀態(tài)重置”，事實(shí)上回溯算法還有一個(gè)話(huà)題就是“剪枝”，我們暫且不展開(kāi)，下面先做已經(jīng)介紹的知識(shí)點(diǎn)做一個(gè)簡(jiǎn)單的總結(jié)。

總結(jié)

回溯算法是在一個(gè)樹(shù)形問(wèn)題上做一次深度優(yōu)先遍歷，用于搜索所有可能的解。

它能解決的問(wèn)題的特點(diǎn)是：1、有若干個(gè)解；2、每一個(gè)解的求解過(guò)程可以分為若干個(gè)步驟（階段），得到所有解的過(guò)程是一個(gè)不斷嘗試的過(guò)程。

為什么使用深度優(yōu)先遍歷？

• 首先是正確性，只有遍歷狀態(tài)空間，才能得到所有符合條件的解；
• 在深度優(yōu)先遍歷的時(shí)候，不同狀態(tài)之間的切換很容易，可以再看一下上面有很多箭頭的那張圖，每?jī)蓚€(gè)狀態(tài)之間的差別只有 1 處，因此回退非常方便，這樣全局就使用一份狀態(tài)變量完成搜索；
• 如果每一個(gè)狀態(tài)都去創(chuàng)建新的變量，時(shí)間復(fù)雜度是 ，并且也有空間的消耗。
• 搜索問(wèn)題的狀態(tài)空間一般很大，在候選數(shù)比較多的時(shí)候，在非葉子結(jié)點(diǎn)上創(chuàng)建新的狀態(tài)變量的性能消耗就很?chē)?yán)重；
• 就本題而言，只需要葉子結(jié)點(diǎn)的那個(gè)狀態(tài)，在葉子結(jié)點(diǎn)執(zhí)行拷貝，時(shí)間復(fù)雜度是 。路徑變量在深度優(yōu)先遍歷的時(shí)候，結(jié)點(diǎn)之間的轉(zhuǎn)換只需要 。

為什么不使用廣度優(yōu)先遍歷？

• 如果使用廣度優(yōu)先遍歷，從淺層轉(zhuǎn)到深層（請(qǐng)讀者想象廣搜的過(guò)程），狀態(tài)的變化就很大，此時(shí)我們不得不在每一個(gè)狀態(tài)都新建變量去保存它，上面已經(jīng)分析過(guò)了，從性能來(lái)說(shuō)是不劃算的；
• 從編寫(xiě)代碼的角度上來(lái)說(shuō)，如果使用廣度優(yōu)先遍歷就得使用隊(duì)列，然后編寫(xiě)結(jié)點(diǎn)類(lèi)。而使用深度優(yōu)先遍歷，我們可以直接使用了系統(tǒng)棧，系統(tǒng)棧幫助我們保存了每一個(gè)結(jié)點(diǎn)的狀態(tài)信息。于是我們不用編寫(xiě)結(jié)點(diǎn)類(lèi)，不必手動(dòng)編寫(xiě)棧完成深度優(yōu)先遍歷。

這道題用廣度優(yōu)先遍歷寫(xiě)是完全可以的，我嘗試過(guò)，代碼寫(xiě)出來(lái)非常不美觀。感興趣的朋友也可以嘗試寫(xiě)一下，嘗試寫(xiě)廣搜的目的是更好地體會(huì)為什么“深搜”能成為強(qiáng)大的“回溯搜索算法”，而廣搜不是。

認(rèn)識(shí)“剪枝”

由于回溯算法的時(shí)間復(fù)雜度很高，因此，在遍歷的時(shí)候，如果能夠提前知道這一條分支不能搜索到滿(mǎn)意的結(jié)果，這一分支就可以跳過(guò)，這一步操作就是在一棵樹(shù)上剪去一個(gè)枝葉，被人們很形象地稱(chēng)之為剪枝。

回溯算法會(huì)大量應(yīng)用“剪枝”技巧達(dá)到以加快搜索速度。這里有幾點(diǎn)提示：

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

2、正是因?yàn)榛厮輪?wèn)題本身時(shí)間復(fù)雜度就很高，所以能用空間換時(shí)間就盡量使用空間。

如果大家玩得轉(zhuǎn)“剪枝”，或許在開(kāi)篇列出的一些簡(jiǎn)單的游戲問(wèn)題就不在話(huà)下了，感興趣的朋友不妨挑戰(zhàn)一下。關(guān)于“剪枝”的技巧，以后有機(jī)會(huì)，我再和大家做一次分享。

復(fù)雜度分析

復(fù)雜度分析：（可以暫時(shí)跳過(guò)，或者永遠(yuǎn)跳過(guò)，不是很重要，為了知識(shí)完整性寫(xiě)在這里。）

說(shuō)明：回溯算法的時(shí)間復(fù)雜度一般都比較高，有些問(wèn)題分析起來(lái)很復(fù)雜，我個(gè)人覺(jué)得沒(méi)有必要掌握，而且剪枝剪得好的話(huà)，復(fù)雜度會(huì)降得很低很多，因此分析最壞時(shí)間復(fù)雜度的意義也不是很大，視情況而定。

• 時(shí)間復(fù)雜度：

首先計(jì)算“非葉子結(jié)點(diǎn)的個(gè)數(shù)”。依次為（按照層數(shù)來(lái)）

說(shuō)明：根結(jié)點(diǎn)為 ，計(jì)算復(fù)雜度的時(shí)候忽略； 表示排列數(shù)，計(jì)算公式為 。

在第 1 層，結(jié)點(diǎn)個(gè)數(shù)為：在 個(gè)數(shù)選 1 個(gè)的排列，即 ；

在第 2 層，結(jié)點(diǎn)個(gè)數(shù)為：在 個(gè)數(shù)選 2 個(gè)的排列，即 。

以此類(lèi)推，全部的非葉子結(jié)點(diǎn)的總數(shù)是：

將常系數(shù) 視為 ，每個(gè)內(nèi)部結(jié)點(diǎn)循環(huán) 次，故非葉子結(jié)點(diǎn)的時(shí)間復(fù)雜度為 ；

然后計(jì)算葉子結(jié)點(diǎn)的個(gè)數(shù)。最后一層共 個(gè)葉節(jié)點(diǎn)，在葉子結(jié)點(diǎn)處拷貝需要 ，葉子結(jié)點(diǎn)的時(shí)間復(fù)雜度也為 。

• 空間復(fù)雜度：。遞歸樹(shù)的深度是 ；全排列的總數(shù)是 ，每個(gè)全排列占空間 ，一共是 這么多空間。取較大者。

練習(xí)

下面提供一些我做過(guò)的“回溯”算法的問(wèn)題，都是特別基礎(chǔ)的使用回溯算法解決的問(wèn)題，以便大家學(xué)習(xí)和理解“回溯算法”。以下提供一個(gè)經(jīng)驗(yàn)：

做回溯搜索問(wèn)題第 1 步都是先畫(huà)圖，畫(huà)圖是非常重要的，只有畫(huà)圖才能幫助我們想清楚遞歸結(jié)構(gòu)，看清楚、想清楚如何剪枝。具體的做法是：就拿題目中的示例，想一想人手動(dòng)操作是怎么做的，一般這樣下來(lái)，這棵遞歸樹(shù)都不難畫(huà)出。

大家在和小伙伴講解回溯算法甚至是和面試官講解回溯算法的時(shí)候，畫(huà)一個(gè)樹(shù)形圖相信也是非常形象的。再過(guò)渡到編碼，相信也是十分自然的事情。

在畫(huà)圖的過(guò)程中需要思考清楚的問(wèn)題有：

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

2、題目需要的解在哪里？是在葉子結(jié)點(diǎn)、還是在非葉子結(jié)點(diǎn)、還是在從跟結(jié)點(diǎn)到葉子結(jié)點(diǎn)的路徑？

3、哪些搜索是會(huì)產(chǎn)生不需要的解的，這里要特別清楚深搜是怎么運(yùn)行的，在深搜的過(guò)程中，狀態(tài)變量發(fā)生了什么變化。例如：產(chǎn)生重復(fù)是什么原因，如果在淺層就知道這個(gè)分支不能產(chǎn)生需要的結(jié)果，應(yīng)該提前剪枝，剪枝的條件是什么，代碼怎么寫(xiě)？

• 這一點(diǎn)也告訴我們，畫(huà)圖可以幫助更清楚地分析代碼的執(zhí)行流程，以準(zhǔn)確捕捉需要剪枝的條件。

擅長(zhǎng)使用

image-20200120041346413

回溯算法基礎(chǔ)問(wèn)題列表

正是由于回溯算法具有“強(qiáng)大的”暴力搜索的能力，它被應(yīng)用于一些游戲問(wèn)題，例如：N 皇后、解數(shù)獨(dú)、祖瑪游戲、24 點(diǎn)游戲、走迷宮、生成迷宮。許多復(fù)雜的、規(guī)模較大的問(wèn)題都可以使用回溯搜索算法得到所有可行解，進(jìn)而得到最優(yōu)解，因此回溯算法有“通用解題方法”的美稱(chēng)，回溯算法也是經(jīng)典的人工智能的基礎(chǔ)算法。

另外，由于執(zhí)行的深度優(yōu)先遍歷，從較深層的結(jié)點(diǎn)返回到較淺層結(jié)點(diǎn)的時(shí)候，需要做“狀態(tài)重置”，即“回到過(guò)去”、“恢復(fù)現(xiàn)場(chǎng)”，我們舉一個(gè)例子：請(qǐng)大家看上面的樹(shù)形圖想象，代碼是如何從葉子結(jié)點(diǎn) [1, 2, 3] 到葉子結(jié)點(diǎn) [1, 3, 2] 的。深度優(yōu)先遍歷是這樣執(zhí)行的：

• 從 [1, 2, 3] 回到 [1, 2] 的時(shí)候，需要撤銷(xiāo)剛剛已經(jīng)選擇的數(shù) 3；
• 由于在上一層只有一個(gè)數(shù) 3 能選擇，我們已經(jīng)嘗試過(guò)了，因此程序回到再上一層，需要撤銷(xiāo)對(duì) 2 的選擇，好讓后面的程序知道，選擇 3 了以后還能夠選擇 2。

使用深度優(yōu)先遍歷編寫(xiě)代碼，可以直接借助系統(tǒng)棧空間，為我們保存所需要的狀態(tài)變量。在編碼中需要注意：遍歷到相應(yīng)的結(jié)點(diǎn)的時(shí)候，狀態(tài)變量的值是必須是正確的。此處我們來(lái)認(rèn)識(shí) path 變量作為狀態(tài)變量，它在深度優(yōu)先遍歷中的變化：往下走一層的時(shí)候，path 變量在尾部追加一個(gè)數(shù)字，而往回走的時(shí)候，需要撤銷(xiāo)上一次的選擇，這一操作也是在 path 的尾部去掉一個(gè)數(shù)字，因此 path 變量是一個(gè)棧。