點(diǎn)贊關(guān)注，不再迷路拌禾，你的支持對(duì)我意義重大取胎！

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

前言

• 回溯算法的思想并不復(fù)雜循榆，但是在回溯基礎(chǔ)上的不少變型題也是面試高頻考點(diǎn)，掌握基本的解題框架很重要墨坚。
• 在這篇文章里秧饮，我將梳理回溯算法的基本概念 & 秤彻遥考題型。如果能幫上忙盗尸，請(qǐng)務(wù)必點(diǎn)贊加關(guān)注柑船，這真的對(duì)我非常重要。

目錄

1. 概述

1.1 回溯思想

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

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

1.2 回溯的三要素

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

回溯就是“走回頭路”

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

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

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 個(gè)排序、第 5 節(jié)島嶼數(shù)量問題中后众，它們?cè)谏顚雍瘮?shù)返回后沒有必要回溯胀糜。

1.3 回溯剪枝

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

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

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

例如：47. Permutations II 全排列 II（用重復(fù)數(shù)字） 這道題給定一個(gè)可包含重復(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
    }
}

然而，因?yàn)樵瓟?shù)組中有兩個(gè) 1 涣楷，所以結(jié)果中會(huì)存在一些重復(fù)排列分唾，怎么去重呢？一種方法是在得到排列之后狮斗，檢查結(jié)果集合中是否已經(jīng)有相同的排列绽乔，這是一個(gè)的比較，顯然是不明智的碳褒。另一種方法就是尋找重復(fù)狀態(tài)折砸，打從一開始就“有先見之明”地避開一些選擇。

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

也就是說删顶，當(dāng)我們發(fā)現(xiàn)兩個(gè)狀態(tài)的路徑和選擇列表完全相同時(shí)，說明這兩個(gè)狀態(tài)是完全重復(fù)的淑廊。以兩個(gè)重復(fù)狀態(tài)為起點(diǎn)進(jìn)行遞歸逗余，最終得到的結(jié)果也一定是重復(fù)的。在這道題里季惩，我們先對(duì)輸入執(zhí)行 快速排序猎荠，在之后的每次選擇之前坚弱，先判斷當(dāng)前狀態(tài)是否與上一個(gè)選擇重復(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)我們?cè)谝粋€(gè)選擇的分支中確定了最終解后输虱，就沒必要去嘗試其他的選擇了些楣。例如在 79. Word Search 單詞搜索 中，當(dāng)確定單詞存在時(shí)宪睹，就沒必要繼續(xù)搜索了愁茁，在 第 4 節(jié) 會(huì)專門分析這道題。

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

• 無效選擇

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

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

3.1 排列 & 組合問題

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

• 排列問題：
  有 3 個(gè)不同的小球 A整袁，B菠齿，C，從中取出 2 個(gè)放稱一排坐昙，有幾種方法绳匀？
• 組合問題：
  有 3 個(gè)不同的小球 A，B炸客，C疾棵，從中取出 2 個(gè)放成一堆，有幾種方法痹仙？

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

從三個(gè)球中取一個(gè)梨州、兩個(gè)、三個(gè)的方法

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

那么每窖，如何排除元素相同帮掉，順序不同的集合呢？這里提一個(gè)很好理解的方法窒典，相信一說出來很多同學(xué)都會(huì)煥然大悟：“我的初中數(shù)學(xué)老師就是這么教我的蟆炊。”

可以看到瀑志，只要避免組合之前的元素涩搓，就可以避免重復(fù)。例如在選擇 {B, }之后劈猪，就不要組合之前的 A 元素了昧甘，否則會(huì)造成重復(fù)。因?yàn)樵?{A, } 的分支里战得，已經(jīng)存在過 {A, B} 的組合了充边。因此，我們可以使用一個(gè) from 變量來標(biāo)示當(dāng)前狀態(tài)允許的選擇列表范圍常侦。

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

復(fù)雜度分析：

• 全排列

總共有個(gè)子問題刮吧，每個(gè)子問題的時(shí)間復(fù)雜度 ，因此總的時(shí)間復(fù)雜度 掖蛤。除了輸出數(shù)組外杀捻，空間復(fù)雜度為 ；

• 組合

總共有 個(gè)子問題蚓庭，每個(gè)子問題的時(shí)間復(fù)雜度 致讥，因此總的時(shí)間復(fù)雜度 。除了輸出數(shù)組外器赞，空間復(fù)雜度為 垢袱；

3.2 字典序排列問題

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

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

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

• 下一個(gè)排列

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

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

• 第 k 個(gè)排列

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

4. 二維平面搜索問題

文章開頭提到的走迷宮問題泣洞，其實(shí)就是在二維平面上的回溯算法問題，終止條件時(shí)當(dāng)前位置為終點(diǎn)默色。既然是回溯算法球凰，怎么都逃不出我們反復(fù)強(qiáng)調(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í)椿每，一個(gè)點(diǎn)的選擇列表就是它的上下左右方向（除了來的方向）伊者，為了方便編碼，可以使用一個(gè)偏移量數(shù)組间护，偏移量數(shù)組內(nèi)的 4 個(gè)偏移的順序是無關(guān)緊要删壮；

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

4.3 檢查邊界

二維平面通常是有邊界的，因此可以寫一個(gè)函數(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é)二維平面搜索問題的進(jìn)階版本亿虽。即：在二維平面上找出滿足條件的相連節(jié)點(diǎn)菱涤。

所謂相連節(jié)點(diǎn)，指的是兩個(gè)節(jié)點(diǎn)上下左右 4 個(gè)方向存在相連的節(jié)點(diǎn)洛勉。有的題目會(huì)擴(kuò)展到 8 個(gè)方向（斜對(duì)角的 4 個(gè)方向）粘秆，不過只是多了幾個(gè)方向而已，沒有很大區(qū)別收毫。例如攻走，下面這幅圖將中心節(jié)點(diǎn)相連的白色方格上色：

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

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

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

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

6. 總結(jié)

回溯算法的思想并不復(fù)雜逛裤，但是確實(shí)高頻考點(diǎn)；熟練掌握回溯算法猴抹，對(duì)于理解動(dòng)態(tài)規(guī)劃算法也很有幫助带族，學(xué)習(xí)優(yōu)先級(jí)較高。

參考資料

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

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