前言

提示：陽光好的時(shí)候，會感覺還可以活很久，甚至可以活出喜悅。 --余秀華

回溯是非常重要的算法思想之一，主要解決一些暴力枚舉也搞不定的問題（這里埋個(gè)坑??）例如組合、分割、子集、棋盤等等。從性能角度來看回溯算法的效率并不是很高，但是對于暴力也解決不了的問題，它往往很快可以出結(jié)果，效率低就可以理解了吧。接下來，就看看回溯的事情吧??

回溯的核心問題

遞歸+局部枚舉+放下前任

接著看這個(gè)題目：77. 組合 - 力扣（LeetCode）

當(dāng)n = 4時(shí)，我們可以選擇的有n有{1，2，3，4}這四種情況，所以我們從第一層到第二層的分支有四個(gè)，分別表示可取1，2，3，4.而且這里從左到右取數(shù)，取過的數(shù)，不在重復(fù)取。第一次取1，集合變?yōu)?，3，4.因?yàn)閗= 2，我們也只能再取1個(gè)數(shù)就可以了，分別取2，3，4.得到的集合就是[1,2]、[1,3]、[1,4]。一次類推：

橫向：

每次從集合中選取元素，可選擇的范圍回逐步收縮，到了取4時(shí)就直接返為空了。

繼續(xù)觀察樹結(jié)構(gòu)，可以發(fā)現(xiàn)，圖中每次訪問到一個(gè)葉子節(jié)點(diǎn)（圖中的標(biāo)記處），我們就可以得到一個(gè)結(jié)果。雖然到最后時(shí)空的，但是不影響最終結(jié)果。這里相當(dāng)于從根節(jié)點(diǎn)開始每次選擇的內(nèi)容（分支）達(dá)到葉子節(jié)點(diǎn)時(shí)，將其收起起來就是我們想要的結(jié)果。

你可以嘗試畫下n=5，k=3的結(jié)果：有沒有感覺

從圖中我們發(fā)現(xiàn)元素個(gè)數(shù)n相當(dāng)于樹的寬度（橫向），而每個(gè)結(jié)果的元素個(gè)數(shù)k相當(dāng)于樹的深度（縱向）。所以我們說回溯問題就是一縱一橫而已。在分析我們回發(fā)現(xiàn)下面幾個(gè)規(guī)律：

• 我們每次選擇都是從類似{1，2，3，4}，{1，2，3，4}這個(gè)樣的序列中一個(gè)一個(gè)選的，這就是為什么說是局部枚舉，后面的枚舉范圍回越來越小。
• 枚舉時(shí)，我們就是簡單的暴露測試而已，一個(gè)一個(gè)驗(yàn)證，能否滿足要求，從上圖可以看到，這就是N叉樹的遍歷過程，一次代碼相似度很高。
• 我們再看葉子過程，這部分是不是和（n = 4，k = 2)處理的結(jié)果一致，也就說是很明顯的遞歸結(jié)構(gòu)。

到此，我們還有一個(gè)問題待解決，就是回溯一般會有一個(gè)手動(dòng)撤銷的操作，為什么要這么做呢？

繼續(xù)觀察縱橫圖：

我們可以看到，我們收集的每個(gè)結(jié)果不是針對葉子節(jié)點(diǎn)的，而是針對樹枝的，比如最上層我們首先確定了1，下層我們?nèi)绻x擇了2，那么結(jié)果就是{1，2}，如果選擇了3，結(jié)果就是{1，3}.一次類推。現(xiàn)在時(shí)怎么確定得到第一個(gè)結(jié)果時(shí){1，2}之后,得到第二個(gè)結(jié)果是{1，3}呢？

繼續(xù)觀察縱橫圖 ，可以看到，我們在得到{1，2}之后將2撤銷，再繼續(xù)使用3，就得到了{(lán)1，3}，同理也可以得到{1,4},之后這一層就沒有了，我們可以撤銷1，繼續(xù)從最上層取2繼續(xù)進(jìn)行。

這里對應(yīng)的代碼操作就是先將第一個(gè)結(jié)果放在臨時(shí)列表的Path里面，得到第一個(gè)結(jié)果{1，2}，之后就將path里面的內(nèi)容放進(jìn)結(jié)果列表resultList中，之后，將path里面的2撤銷掉，繼續(xù)尋找下一個(gè)結(jié)果{1，3}，繼續(xù)將path加入resultList中，然后再次撤銷，繼續(xù)尋找。

現(xiàn)在了解為什么要撤銷，看圖。這個(gè)過程，我們稱它“放下前任，繼續(xù)前進(jìn)”，后面的回溯大都是這樣的思路。

這幾條就是回溯的基本規(guī)律，了解這一點(diǎn)，我們就可以看看代碼是怎么回事了，到此我們看看完整的代碼時(shí)怎樣的：

 public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> res = new ArrayList<>();
        if (k <=0 || n < k){
            return res;
        }
?
        Deque<Integer> path = new ArrayDeque<>();
?
        dfs(n,k,1,path,res);
        return res;
    }
?
    public void dfs(int n,int k,int startIndex,Deque<Integer> path,List<List<Integer>> res){
        // 遞歸終止條件，path 等于k（剛好完成一次
        if (path.size() == k){
            res.add((new ArrayList<>(path)));
            return;
        }
        // 針對每個(gè)節(jié)點(diǎn)，這里就是遍歷搜索，也就是枚舉
        for(int i = startIndex; i <= n; i++){
            // 向路徑里添加一個(gè)數(shù)（分支里的取值
            path.addLast(i);
            // 搜索起點(diǎn)要加1，就是縮小范圍，準(zhǔn)備下一輪遞歸（這里不允許重復(fù)
            dfs(n,k,i + 1,path,res);
            // 遞歸之后要做同樣的逆向操作，撤銷掉
            path.removeLast();
        }
    }

上面代碼還有一個(gè)問題需要解釋：startIndex和i是怎么變化的，為什么要傳遞到下一層（+ 1）

我們來看看這里的遞歸循環(huán)：

   // 針對每個(gè)節(jié)點(diǎn)，這里就是遍歷搜索，也就是枚舉
        for(int i = startIndex; i <= n; i++){
            // 向路徑里添加一個(gè)數(shù)（分支里的取值
            path.addLast(i);
            // 搜索起點(diǎn)要加1，就是縮小范圍，準(zhǔn)備下一輪遞歸（這里不允許重復(fù)
            dfs(n,k,i + 1,path,res);
            // 遞歸之后要做同樣的逆向操作，撤銷掉
            path.removeLast();
        }

這里的循環(huán)有什么作用呢？看看這里，其實(shí)來說是一個(gè)枚舉，第一次n=4，可以選擇1，2，3，4四種情況，所以就存在4個(gè)分支，for就需要執(zhí)行4次：

對于第二層來說，第一個(gè)數(shù)，選擇1之后，身下的元素就只有2，3，4了。所以這時(shí)候for循環(huán)就執(zhí)行3次，后面的只有2次和1次了。

撤銷操作解釋

如果你還是不清楚的話，這里就帶圖詳細(xì)的走一遍，回溯也就是這個(gè)地方有點(diǎn)暈，拿下就是勝利?。

   // 針對每個(gè)節(jié)點(diǎn)，這里就是遍歷搜索，也就是枚舉
        for(int i = startIndex; i <= n; i++){
            // 向路徑里添加一個(gè)數(shù)（分支里的取值
            path.addLast(i);
            // 搜索起點(diǎn)要加1，就是縮小范圍，準(zhǔn)備下一輪遞歸（這里不允許重復(fù)
            dfs(n,k,i + 1,path,res);
            // 遞歸之后要做同樣的逆向操作，撤銷掉
            path.removeLast();
        }

為什么要remove呢？看下圖，當(dāng)?shù)谝粚尤?時(shí)，最底層的遍歷從左到右執(zhí)行，取2，取3，取4.而取3的時(shí)候，此時(shí)res里面存儲的是{1，2}，所以這里前提是需要撤銷掉2(path.removeLast();)的作用。

這里我們拆解一下遞歸方法，將遞歸拆分成函數(shù)調(diào)用，輸出第一條路徑{1，2}的步驟如下：

我們在遞歸說過一個(gè)特點(diǎn)：不到南墻不回頭，回溯也是這個(gè)道理，我們看看這個(gè)過程。

然后，怎么在次進(jìn)行呢，這里就需要撤回一下了，但是如果將這里的remove代碼去掉，就會是這個(gè)樣子：

這里知道遍歷完成，然會的就不做撤銷，就會下一場進(jìn)入for循環(huán)，也就是回變成{1，2，3}.

path是一個(gè)全局的引用的，各個(gè)遞歸的函數(shù)是公用的，所以這里處理完{1，2}，之后，需要把2撤出去，將1保留，再讓三進(jìn)入，從而得到{1，3}.所以這里不許remove一下的。

同樣處理完之后，后續(xù)的也是依次處理，需要撤銷的，這里也就是不得不處理撤銷的操作。

總結(jié)

提示：什么叫回溯；保留狀態(tài)；撤銷操作；回溯核心思想；回溯的入門

如果有幫助到你，請給題解點(diǎn)個(gè)贊和收藏，讓更多的人看到 ~ ("▔□▔)/

如有不理解的地方，歡迎你在評論區(qū)給我留言，我都會逐一回復(fù) ~

也歡迎你 關(guān)注我 ，喜歡交朋友，喜歡一起探討問題。

文章來源地址http://www.zghlxwxcb.cn/news/detail-741507.html

到了這里，關(guān)于算法通過村第十八關(guān)-回溯|青銅筆記|什么叫回溯（中篇）的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！