回溯法理論知識

回溯法也可以叫做回溯搜索法，它是一種搜索的方式?；厮菔沁f歸的副產(chǎn)品，只要有遞歸就會有回溯。所以回溯函數(shù)也就是遞歸函數(shù)，指的都是一個函數(shù)。

回溯法的效率

回溯法并不是什么高效的算法。因為回溯的本質(zhì)是窮舉，窮舉所有可能，然后選出我們想要的答案，如果想讓回溯法高效一些，可以加一些剪枝的操作，但也改不了回溯法就是窮舉的本質(zhì)。

既然回溯法并不高效為什么還要用它呢？因為沒得選，一些問題能暴力搜出來就不錯了，撐死了再剪枝一下，還沒有更高效的解法。

回溯法解決的問題

回溯法，一般可以解決如下幾種問題：

• 組合問題：N個數(shù)里面按一定規(guī)則找出k個數(shù)的集合
• 切割問題：一個字符串按一定規(guī)則有幾種切割方式
• 子集問題：一個N個數(shù)的集合里有多少符合條件的子集
• 排列問題：N個數(shù)按一定規(guī)則全排列，有幾種排列方式
• 棋盤問題：N皇后，解數(shù)獨等等

以上每個問題，都不簡單！

如何理解回溯法

回溯法解決的問題都可以抽象為樹形結(jié)構(gòu)。因為回溯法解決的都是在集合中遞歸查找子集，集合的大小就構(gòu)成了樹的寬度，遞歸的深度，都構(gòu)成的樹的深度。遞歸就要有終止條件，所以必然是一棵高度有限的樹（N叉樹）。

回溯法模板

這里給出卡哥總結(jié)的回溯算法模板。

回溯三部曲：

?1.回溯函數(shù)模板返回值以及參數(shù)

在回溯算法中，函數(shù)起名字為backtracking，回溯算法中函數(shù)返回值一般為void。

再來看一下參數(shù)，因為回溯算法需要的參數(shù)可不像二叉樹遞歸的時候那么容易一次性確定下來，所以一般是先寫邏輯，然后需要什么參數(shù)，就填什么參數(shù)。

2.回溯函數(shù)終止條件

既然是樹形結(jié)構(gòu)，遍歷樹形結(jié)構(gòu)一定要有終止條件。一般來說搜到葉子節(jié)點了，也就找到了滿足條件的一條答案，把這個答案存放起來，并結(jié)束本層遞歸。

?3.回溯搜索的遍歷過程

回溯法一般是在集合中遞歸搜索，集合的大小構(gòu)成了樹的寬度，遞歸的深度構(gòu)成的樹的深度。

for循環(huán)可以理解是橫向遍歷，backtracking（遞歸）就是縱向遍歷，這樣就把這棵樹全遍歷完了，一般來說，搜索葉子節(jié)點就是找的其中一個結(jié)果了。

分析完過程，回溯算法模板框架如下：

void backtracking(參數(shù)) {if (終止條件) {存放結(jié)果;return;}for (選擇：本層集合中元素（樹中節(jié)點孩子的數(shù)量就是集合的大小）) {處理節(jié)點;backtracking(路徑，選擇列表); // 遞歸回溯，撤銷處理結(jié)果}
}

算法題

Leetcode ?77. 組合

題目鏈接:77. 組合

大佬視頻講解：組合視頻講解

個人思路

組合問題就是不能使得結(jié)果重復(fù)，只能暴力解法，使用遞歸循環(huán)再加回溯來解決。

解法

先回顧一下組合和排列。組合是不強調(diào)元素順序的，排列是強調(diào)元素順序。

例如：{1, 2} 和 {2, 1} 在組合上，就是一個集合，因為不強調(diào)順序，而要是排列的話，{1, 2} 和 {2, 1} 就是兩個集合了。

記住組合無序，排列有序，就可以了。

回溯法

把組合問題抽象為如下樹形結(jié)構(gòu)

每次從集合中選取元素，可選擇的范圍隨著選擇的進(jìn)行而收縮，調(diào)整可選擇的范圍。所以輸入的n相當(dāng)于樹的寬度，k相當(dāng)于樹的深度。每次搜索到了葉子節(jié)點，就找到了一個結(jié)果。所以把達(dá)到葉子節(jié)點的結(jié)果收集起來，就可以求得 n個數(shù)中k個數(shù)的組合集合。

回溯法三部曲

1.遞歸函數(shù)的返回值以及參數(shù)

在這里要定義兩個全局變量，一個用來存放符合條件單一結(jié)果，一個用來存放符合條件結(jié)果的集合。函數(shù)里一定有兩個參數(shù)，既然是集合n里面取k個數(shù)，那么n和k是兩個int型的參數(shù)。

然后還需要一個參數(shù)，為int型變量startIndex；startIndex用來記錄下一層遞歸，搜索的起始位置，來防止出現(xiàn)重復(fù)的組合。

從下圖中紅線部分可以看出，在集合[1,2,3,4]取1之后，下一層遞歸，就要在[2,3,4]中取數(shù)了，那么下一層遞歸如何知道從[2,3,4]中取數(shù)呢，靠的就是startIndex。

2.回溯函數(shù)終止條件

到達(dá)葉子節(jié)點就找到一個結(jié)果，即path這個數(shù)組的大小如果達(dá)到k，說明找到了一個子集大小為k的組合了，在圖中path存的就是根節(jié)點到葉子節(jié)點的路徑。此時用result二維數(shù)組，把path保存起來，并終止本層遞歸。

3.單層搜索的過程

回溯法的搜索過程就是一個樹型結(jié)構(gòu)的遍歷過程

在上圖中，可以看出for循環(huán)用來橫向遍歷，遞歸的過程是縱向遍歷。for循環(huán)每次從startIndex開始遍歷，然后用path保存取到的節(jié)點i。而backtracking（遞歸函數(shù)）通過不斷調(diào)用自己一直往深處遍歷，總會遇到葉子節(jié)點，遇到了葉子節(jié)點就要返回。backtracking的下面部分就是回溯的操作了，撤銷本次處理的結(jié)果。

class Solution {List<List<Integer>> result= new ArrayList<>();LinkedList<Integer> path = new LinkedList<>();public List<List<Integer>> combine(int n, int k) {backtracking(n,k,1);return result;}//startIndex 用來記錄本層遞歸的中，集合從哪里開始遍歷public void backtracking(int n,int k,int startIndex){if (path.size() == k){//終止條件result.add(new ArrayList<>(path));return;}for (int i =startIndex;i<=n;i++){//橫向遍歷path.add(i);//加入結(jié)果集backtracking(n,k,i+1);//遞歸:縱向遍歷path.removeLast();//回溯}}
}

時間復(fù)雜度:O(n * 2^n))；（循環(huán)n個元素，2^n表示所有可能的子集數(shù)量）

空間復(fù)雜度:O(n);（遞歸棧的深度最多為 n）

上面代碼和這個 模板基本一樣,這就是后續(xù)做回溯法的模板代碼了！

void backtracking(參數(shù)) {if (終止條件) {存放結(jié)果;return;}for (選擇：本層集合中元素（樹中節(jié)點孩子的數(shù)量就是集合的大小）) {處理節(jié)點;backtracking(路徑，選擇列表); // 遞歸回溯，撤銷處理結(jié)果}
}

回溯剪枝優(yōu)化

如何優(yōu)化得畫圖來看。舉一個例子，n = 4，k = 4的話，那么第一層for循環(huán)的時候，從元素2開始的遍歷都沒有意義了。 在第二層for循環(huán)，從元素3開始的遍歷都沒有意義了。

圖中每一個節(jié)點，就代表本層的一個for循環(huán)，那么每一層的for循環(huán)從第二個數(shù)開始遍歷的話，都沒有意義，都是無效遍歷。所以，可以剪枝的地方就在遞歸中每一層的for循環(huán)所選擇的起始位置。如果for循環(huán)選擇的起始位置之后的元素個數(shù) 已經(jīng)不足 題目需要的元素個數(shù)了，那么就沒有必要搜索了。

注意以下代碼中的i，就是for循環(huán)里選擇的起始位置。

接下來看一下優(yōu)化過程如下：

1. 已經(jīng)選擇的元素個數(shù)：path.size();

2. 還需要的元素個數(shù)為: k - path.size();

3. 在集合n中至多要從該起始位置 : n - (k - path.size()) + 1，開始遍歷

這樣之所以需要+1，是因為包括起始位置，需要是一個左閉的集合。?

舉個例子，n = 4，k = 3， 目前已經(jīng)選取的元素為0（path.size為0），n - (k - 0) + 1 即 4 - ( 3 - 0) + 1 = 2。那么從2開始搜索都是合理的，可以是組合[2, 3, 4]。

class Solution {List<List<Integer>> result = new ArrayList<>();LinkedList<Integer> path = new LinkedList<>();public List<List<Integer>> combine(int n, int k) {combineHelper(n, k, 1);return result;}//startIndex用來記錄本層遞歸的中，集合從哪里開始遍歷private void combineHelper(int n, int k, int startIndex){//終止條件if (path.size() == k){result.add(new ArrayList<>(path));return;}for (int i = startIndex; i <= n - (k - path.size()) + 1; i++){path.add(i);//加入結(jié)果集combineHelper(n, k, i + 1);//遞歸path.removeLast();//回溯}}
}

時間復(fù)雜度:O(n * 2^n))；（循環(huán)n個元素，2^n表示所有可能的子集數(shù)量）

空間復(fù)雜度:O(n);（遞歸棧的深度最多為 n）

以上是個人的思考反思與總結(jié)，若只想根據(jù)系列題刷，參考卡哥的網(wǎng)址代碼隨想錄算法官網(wǎng)