點贊關(guān)注，不再迷路，你的支持對我意義重大！

?? Hi，我是丑丑。本文「數(shù)據(jù)結(jié)構(gòu) & 算法」| 導(dǎo)讀 —— 登高博見 已收錄，這里有 Android 進階成長路線筆記 & 博客，歡迎跟著彭丑丑一起成長。（聯(lián)系方式在 GitHub）

前言

• 回溯算法的思想并不復(fù)雜，但是在回溯基礎(chǔ)上的不少變型題也是面試高頻考點，掌握基本的解題框架很重要。
• 在這篇文章里，我將梳理回溯算法的基本概念 & 常考題型。如果能幫上忙，請務(wù)必點贊加關(guān)注，這真的對我非常重要。

目錄

1. 概述

1.1 回溯思想

回溯算法（Backtrack）是一種試錯思想，本質(zhì)上是深度優(yōu)先搜索。即：從問題的某一種狀態(tài)出發(fā)，依次嘗試現(xiàn)有狀態(tài)可以做出的選擇從而進入下一個狀態(tài)。遞歸這個過程，如果在某個狀態(tài)無法做更多選擇，或者已經(jīng)找到目標(biāo)答案時，則回退一步甚至多步重新嘗試，直到最終所有選擇都嘗試過。

整個過程就像走迷宮一樣，當(dāng)我們遇到一個分叉口時，可以選擇從一個方向進去嘗試。如果走到死胡同則返回上一個分叉口，選擇另外一條方向繼續(xù)嘗試，直到發(fā)現(xiàn)沒有出口，或者找到出口。

1.2 回溯的三要素

理解了回溯算法的思想，下面我們來分析回溯的關(guān)鍵點。在回溯算法中，需要考慮三個要素：路徑、選擇列表、結(jié)束條件，以走迷宮為例：

回溯就是“走回頭路”

• 1. 路徑：已經(jīng)做出的選擇
• 2. 選擇列表：當(dāng)前狀態(tài)可以做出的選擇
• 3. 結(jié)束條件：選擇列表為空，或者找到目標(biāo)

要走出這個迷宮，我們需要重復(fù)做一件事：選擇從一個方向進去嘗試。如果走到死胡同則返回上一個分叉口，選擇另外一條方向繼續(xù)嘗試。用程序?qū)崿F(xiàn)出來，這個重復(fù)做的事就是遞歸函數(shù)，實際中我們可以遵循一個解題模板 & 思路：

fun backtrack(){
    1. 判斷當(dāng)前狀態(tài)是否滿足終止條件
    if(終止條件){
        return solution
    }
    2. 否則遍歷選擇列表
    for(選擇 in 選擇列表){
        3. 做出選擇
        solution.push(選擇)
        4. 遞歸
        backtrack()
        5. 回溯（撤銷選擇）
        stack.pop(選擇)
    }
}

需要注意的是，解題框架 & 思路不是死板的，應(yīng)根據(jù)具體問題具體分析。例如：回溯（撤銷選擇）并不是必須的，第 3.2 節(jié)第 k 個排序、第 5 節(jié)島嶼數(shù)量問題中，它們在深層函數(shù)返回后沒有必要回溯。

1.3 回溯剪枝

由于回溯算法的時間復(fù)雜度非常高，當(dāng)我們遇到一個分支時，如果“有先見之明”，能夠知道某個選擇最終一定無法找到答案，那么就不應(yīng)該去嘗試走這條路徑，這個步驟叫作剪枝。

那么，怎么找到這個“先見之明”呢？經(jīng)過我的總結(jié)，大概有以下幾種情況：

• 重復(fù)狀態(tài)

例如：47. Permutations II 全排列 II（用重復(fù)數(shù)字） 這道題給定一個可包含重復(fù)數(shù)字的序列，要求返回所有不重復(fù)的全排列，例如輸入[1,1,2]預(yù)期的輸出為[1,1,2]、[1,2,1]、[2,1,1]。用我們前面介紹的解題模板，這道題并不難：

class Solution {
    fun permute(nums: IntArray): List<List<Int>> {
        val result = ArrayList<List<Int>>()

        // 選擇列表
        val useds = BooleanArray(nums.size) { false }
        // 路徑
        val track = LinkedList<Int>()

        fun backtrack() {
            // 終止條件
            if (track.size == nums.size) {
                result.add(ArrayList<Int>(track))
                return
            }
            for ((index, used) in useds.withIndex()) {
                if (!used) {
                    // 做出選擇
                    track.push(nums[index])
                    useds[index] = true
                    backtrack()
                    // 回溯
                    track.pop()
                    useds[index] = false
                }
            }
        }

        backtrack()

        return result
    }
}

然而，因為原數(shù)組中有兩個 1 ，所以結(jié)果中會存在一些重復(fù)排列，怎么去重呢？一種方法是在得到排列之后，檢查結(jié)果集合中是否已經(jīng)有相同的排列，這是一個的比較，顯然是不明智的。另一種方法就是尋找重復(fù)狀態(tài)，打從一開始就“有先見之明”地避開一些選擇。

我們先說說什么是重復(fù)狀態(tài)？還記得我們說的回溯三要素嗎：路徑、選擇列表、結(jié)束條件。通常來說，在這三個要素里面結(jié)束條件是固定的，而路徑和選擇列表會隨著每次選擇 & 回溯而變化。

也就是說，當(dāng)我們發(fā)現(xiàn)兩個狀態(tài)的路徑和選擇列表完全相同時，說明這兩個狀態(tài)是完全重復(fù)的。以兩個重復(fù)狀態(tài)為起點進行遞歸，最終得到的結(jié)果也一定是重復(fù)的。在這道題里，我們先對輸入執(zhí)行 快速排序，在之后的每次選擇之前，先判斷當(dāng)前狀態(tài)是否與上一個選擇重復(fù)，是則直接跳過。

[1]與[1`]重復(fù)，[2,1]與[2`,1]重復(fù)，最終得到重復(fù)結(jié)果

class Solution {
    fun permuteUnique(nums: IntArray): List<List<Int>> {

        val result = ArrayList<LinkedList<Int>>()
        if(nums.size <= 0){
            result.add(LinkedList<Int>())
            return result
        }

        // 排序
        Arrays.sort(nums)

        // 選擇列表
        val used = BooleanArray(nums.size){false}
        // 路徑
        val track = LinkedList<Int>()

        fun backtrack(){
            // 終止條件
            if(track.size >= nums.size){
                result.add(LinkedList<Int>(track))
                return
            }
            
            for((index,num) in nums.withIndex()){
                if(used[index]){
                    continue
                }
                if(index > 0 && !used[index - 1] && nums[index] == nums[index - 1]){
                    continue
                }
                // 做出選擇
                used[index] = true
                track.push(num)
                // 遞歸
                backtrack()
                // 回溯
                used[index] = false
                track.pop()
            }
        }

        backtrack()
        
        return result
    }
}

• 最終解確定

當(dāng)我們在一個選擇的分支中確定了最終解后，就沒必要去嘗試其他的選擇了。例如在 79. Word Search 單詞搜索 中，當(dāng)確定單詞存在時，就沒必要繼續(xù)搜索了，在 第 4 節(jié) 會專門分析這道題。

fun backtrack(...){
    for (選擇 in 選擇列表) {
        1. 做出選擇
        2. 遞歸
        val match = backtrack(...)
        3. 回溯
        if (match) {
            return true
        }
    }
}

• 無效選擇

當(dāng)我們可以根據(jù)已知條件判斷某個選擇無法找到最終解時，就沒必要去嘗試這個選擇了。例如：39. Combination Sum 組合總和、60. Permutation Sequence 第 k 個排列

3. 排列 & 組合 & 子集問題

3.1 排列 & 組合問題

排列（permutation）& 組合（combination）& 子集（subset）可以說是回溯算法里最常規(guī)的問題了。其中，子集問題本質(zhì)上也是組合問題。我們先通過一個簡單的問題帶大家體會 排列 & 組合 的區(qū)別：

• 排列問題：
  有 3 個不同的小球 A，B，C，從中取出 2 個放稱一排，有幾種方法？
• 組合問題：
  有 3 個不同的小球 A，B，C，從中取出 2 個放成一堆，有幾種方法？

一排和一堆的區(qū)別是什么呢？很明顯，一排是有順序的，而一堆是無順序的。例如 [A B C] 和 [A C B] 是不同的，而 {A B C} 和 {A C B} 是相同的。

從三個球中取一個、兩個、三個的方法

從上面這張圖里，其實可以清楚地看到，組合問題是在排列問題的基礎(chǔ)上去除重復(fù)集合；子集問題是合并了多個不同規(guī)模的組合問題。

那么，如何排除元素相同，順序不同的集合呢？這里提一個很好理解的方法，相信一說出來很多同學(xué)都會煥然大悟：“我的初中數(shù)學(xué)老師就是這么教我的?！?/p>

可以看到，只要避免組合之前的元素，就可以避免重復(fù)。例如在選擇 {B, }之后，就不要組合之前的 A 元素了，否則會造成重復(fù)。因為在 {A, } 的分支里，已經(jīng)存在過 {A, B} 的組合了。因此，我們可以使用一個 from 變量來標(biāo)示當(dāng)前狀態(tài)允許的選擇列表范圍。

下面給出從 n 個數(shù)中取 k 的數(shù)的排列 & 組合代碼，由于遞歸解法代碼的可解釋性更強，讀者應(yīng)優(yōu)先保證可以熟練地寫出遞歸解法：

復(fù)雜度分析：

• 全排列

總共有個子問題，每個子問題的時間復(fù)雜度 ，因此總的時間復(fù)雜度 。除了輸出數(shù)組外，空間復(fù)雜度為 ；

• 組合

總共有 個子問題，每個子問題的時間復(fù)雜度 ，因此總的時間復(fù)雜度 。除了輸出數(shù)組外，空間復(fù)雜度為 ；

3.2 字典序排列問題

在排列問題中，還有一個字典序排列（Dictionary order）的概念，即：基于字母順序排列，就像單詞在字典中的排列順序一樣，例如 [A B C] 排在 [A C B] 之前。要得到字典序的全排列，遞歸解法和非遞歸解法都可以實現(xiàn)。

使用遞歸解法，只需要保證選擇列表按照字母排序，最終得到的全排列就是字典序排序，實現(xiàn)起來也比較簡單直觀，在 第 1.4 節(jié) 已經(jīng)給出答案了。

使用非遞歸解法的基本思想是：從當(dāng)前字符串出發(fā)，直接找出字典序下一個排列，例如從 [A B C] 直接找到下一個排列 [A C B]。怎么找呢，可以先簡單思考下這個問題：

• 下一個排列

31. Next Permutation 下一個排列 將給定數(shù)字序列重新排列成字典序中下一個更大的排列。

理解了下一個排列的算法之后，寫出全排列的算法就不難了。只需要從第一個排列開始依次輸出下一個排列，最終就得到了字典序全排列。有興趣可以到上一節(jié)的題解中查看，這里就不貼出來了。

• 第 k 個排列

除了求下一個排列外，求第 k 個排列也是很常見了。例如：60. Permutation Sequence 第 k 個排列、440. K-th Smallest in Lexicographical Order 字典序的第K小數(shù)字。基本思想是：通過計算階乘，提前知道這一個分支的葉子節(jié)點個數(shù)，如果 k 不在這個分支上則剪枝：

4. 二維平面搜索問題

文章開頭提到的走迷宮問題，其實就是在二維平面上的回溯算法問題，終止條件時當(dāng)前位置為終點。既然是回溯算法，怎么都逃不出我們反復(fù)強調(diào)的三要素：路徑 & 選擇列表 & 終止條件：

4.1 路徑 - 二維數(shù)組 useds

在全排列問題中，我們使用了一維布爾數(shù)組 used，用來標(biāo)記已經(jīng)走過的路徑。同樣地，在二維平面里，我們需要使用二維布爾數(shù)組，來標(biāo)記已經(jīng)走過的路徑。

1. 一維數(shù)組 int[] useds
2. 二維數(shù)組 int[][] useds

4.2 選擇列表 - 偏移量數(shù)組

在二維平面上搜索時，一個點的選擇列表就是它的上下左右方向（除了來的方向），為了方便編碼，可以使用一個偏移量數(shù)組，偏移量數(shù)組內(nèi)的 4 個偏移的順序是無關(guān)緊要；

int[][] direction = {{-1, 0}, {0, -1}, {0, 1}, {1, 0}};

4.3 檢查邊界

二維平面通常是有邊界的，因此可以寫一個函數(shù)判斷當(dāng)前輸入位置是否越界：

private boolean check(int row, int column) {
    return row >= 0 && row < m && column >= 0 && column < n;
}

有了前面的鋪墊，我們來看這道題：79. Word Search 單詞搜索 就比較好理解了。

5. Flood Fill 問題

Flood Fill（泛洪填充，或稱 Seed Fill 種子填充），是上一節(jié)二維平面搜索問題的進階版本。即：在二維平面上找出滿足條件的相連節(jié)點。

所謂相連節(jié)點，指的是兩個節(jié)點上下左右 4 個方向存在相連的節(jié)點。有的題目會擴展到 8 個方向（斜對角的 4 個方向），不過只是多了幾個方向而已，沒有很大區(qū)別。例如，下面這幅圖將中心節(jié)點相連的白色方格上色：

填充顏色到連通的白色方格

整個解題框架與上一節(jié)的 二維平面搜索問題 大體相同，這里著重講解另一種解法：并查集，在這篇文章里，我們已經(jīng)詳細講解過并查集的使用場景與解題技巧：《數(shù)據(jù)結(jié)構(gòu)面試題 | 并查集 & 聯(lián)合 - 查找算法》

簡單來說：并查集適用于處理不相交集合的連通性問題，這正適用于解決 Flood Fill 的連通問題。我們可以將與中心節(jié)點相連的節(jié)點合并到同一個分量中，全部處理完成后，通過查詢并查集便可判斷兩個節(jié)點是否處于相連：

提示： 同時使用路徑壓縮和按秩合并，查詢的時間復(fù)雜度接近

6. 總結(jié)

回溯算法的思想并不復(fù)雜，但是確實高頻考點；熟練掌握回溯算法，對于理解動態(tài)規(guī)劃算法也很有幫助，學(xué)習(xí)優(yōu)先級較高。

參考資料

• 《回溯法》 —— 維基百科
• 《Flood Fill》 —— 維基百科
• 《回溯算法入門級詳解 + 練習(xí)（全排列 I）》 —— liweiwei 著
• 《回溯搜索 + 剪枝（全排列 II）》 —— liweiwei 著
• 《在二維平面上使用回溯法（單詞搜索 I）》 —— liweiwei 著
• 《回溯算法》 —— liweiwei 著
• 《回溯算法詳解》 —— labuladong 著
• 《FloodFill算法詳解及應(yīng)用》 —— labuladong 著
• 《數(shù)據(jù)結(jié)構(gòu)與算法之美》 —— 王爭 著，極客時間 出品
• 《300分鐘搞定算法面試》 —— 力扣&拉勾網(wǎng) 出品

創(chuàng)作不易，你的「三連」是丑丑最大的動力，我們下次見！