前一節課講解了幾種經典的排序算法。面試主要考察的是分析和處理問題的能力，而排序算法的一些思想是非常常用的，例如歸并排序和快速排序采用的分治法就是高效的算法思想。這節課將介紹：遞歸和回溯。
遞歸和回溯的關系密不可分：
* 遞歸的基本性質就是函數調用，在處理問題的時候，遞歸往往是把一個大規模的問題不斷地變小然后進行推導的過程。
* 回溯則是利用遞歸的性質，從問題的起始點出發，不斷地進行嘗試，回頭一步甚至多步再做選擇，直到最終抵達終點的過程。
* [ ] 遞歸（Recursion）
* 算法思想
遞歸算法是一種調用自身函數的算法（二叉樹的許多性質在定義上就滿足遞歸）。
舉例：（漢諾塔問題）有三個塔 A、B、C，一開始的時候，在塔 A 上放著 n 個盤子，它們自底向上按照從大到小的順序疊放。現在要求將塔 A 中所有的盤子搬到塔 C 上，讓你打印出搬運的步驟。在搬運的過程中，每次只能搬運一個盤子，另外，任何時候，無論在哪個塔上，大盤子不能放在小盤子的上面。
解法：
從最終的結果出發，要把 n 個盤子按照大小順序疊放在塔 C 上，就需要將塔 A 的底部最大的盤子搬到塔 C；
為了實現步驟 1，需要將除了這個最大盤子之外的其余盤子都放到塔 B 上。
由上可知，將原來的問題規模從 n 個盤子變成了 n-1 個盤子，即將 n-1 個盤子轉移到塔 B 上。
如果一個函數，能將 n 個盤子從塔 A，借助塔 B，搬到塔 C。那么，也可以利用該函數將 n-1 個盤子從塔 A，借助塔 C，搬到塔 B。同理，不斷地把問題規模變小，當 n 為 1，也就是只有 1 個盤子的時候，直接打印出步驟。
代碼：
```
void?hano(char?A,?char?B,?char?C,?int?n)?{
????if?(n?>?0)?{
????????hano(A,?C,?B,?n?-?1);
????????move(A,?C);
????????hano(B,?A,?C,?n?-?1);
??}
}
```
由上述總結出遞歸的算法思想，將一個問題的規模變小，然后再利用從小規模問題中得出的結果，結合當前的值或者情況，得出最終的結果。
通俗來說，把要實現的遞歸函數看成是已經實現好的， 直接利用解決一些子問題，然后需要考慮的就是如何根據子問題的解以及當前面對的情況得出答案。這種算法也被稱為自頂向下（Top-Down）的算法。
* [ ] 例題分析一
LeetCode 第 91 題，解碼的方法。
一條包含字母?A-Z?的消息通過以下方式進行了編碼：
```
'A' -> 1
'B' -> 2
…
'Z' -> 26
```
給定一個只包含數字的非空字符串，請計算解碼方法的總數。
**解題思路**
就例題中的第二個例子，給定編碼后的消息是字符串“226”，如果對其中“22”的解碼有 m 種可能，那么，加多一個“6”在最后，相當于在最終解密出來的字符串里多了一個“F”字符而已，總體的解碼還是只有 m 種。
對于“6”而言，如果它的前面是”1”或者“2”，那么它就有可能是“16”，“26”，所以還可以再往前看一個字符，發現它是“26”。而前面的解碼組合是 k 個，那么在這 k 個解出的編碼里，添加一個“Z”，所以總的解碼個數就是 m+k。
**代碼實現**
```
int?numDecodings(String?s)?{
????if?(s.charAt(0)?==?'0')?return?0;
????char[]?chars?=?s.toCharArray();
????return?decode(chars,?chars.length?-?1);
}
//?字符串轉換成字符數組，利用遞歸函數?decode，從最后一個字符向前遞歸
int?decode(char[]?chars,?int?index)?{
????//?處理到了第一個字符,只能有一種解碼方法，返回?1
????if?(index?<=?0)?return?1;
????????
????int?count?=?0;
????????
????char?curr?=?chars[index];
????char?prev?=?chars[index?-?1];
???
????//?當前字符比?“0”?大，則直接利用它之前的字符串所求得的結果?????
????if?(curr?>?'0')?{
????????count?=?decode(chars,?index?-?1);
????}
???
????//?由前一個字符和當前字符所構成的數字，值必須要在?1?到?26?之間，否則無法進行解碼?
????if?(prev?==?'1'?||?(prev?==?'2'?&&?curr?<=?'6'))?{
????????count?+=?decode(chars,?index?-?2);
????}
????????
????return?count;
}
```
**解題模板**
通過上述例題，來歸納總結一下遞歸函數的解題模版。
**解題步驟**
1. 判斷當前情況是否非法，如果非法就立即返回，這一步也被稱為完整性檢查（Sanity Check）。例如，看看當前處理的情況是否越界，是否出現了不滿足條件的情況。通常，這一部分代碼都是寫在最前面的。
2. 判斷是否滿足結束遞歸的條件。在這一步當中，處理的基本上都是一些推導過程當中所定義的初始情況。
3. 將問題的規模縮小，遞歸調用。在歸并排序和快速排序中，我們將問題的規模縮小了一半，而在漢諾塔和解碼的例子中，我們將問題的規模縮小了一個。
4. 利用在小規模問題中的答案，結合當前的數據進行整合，得出最終的答案。
**代碼實現**
```
function?fn(n)?{
????//?第一步：判斷輸入或者狀態是否非法？
????if?(input/state?is?invalid)?{
????????return;
????}
????//?第二步：判讀遞歸是否應當結束?
????if?(match?condition)?{
????????return?some?value;
????}
????//?第三步：縮小問題規模
????result1?=?fn(n1)
????result2?=?fn(n2)
????...
????//?第四步:?整合結果
????return?combine(result1,?result2)
}
```
* [ ] 例題分析二
LeetCode 第 247 題：找到所有長度為 n 的中心對稱數。
**示例**
```
輸入:? n = 2
輸出: ["11","69","88","96"]
```
**解題思路**
* 當 n=0 的時候，應該輸出空字符串：“ ”。
* 當 n=1 的時候，也就是長度為 1 的中心對稱數有：0，1，8。
* 當 n=2 的時候，長度為 2 的中心對稱數有：11， 69，88，96。注意：00 并不是一個合法的結果。
* 當 n=3 的時候，只需要在長度為 1 的合法中心對稱數的基礎上，不斷地在兩邊添加 11，69，88，96 就可以了。
```
[101, 609, 808, 906, ? ? 111, 619, 818, 916, ? ? 181, 689, 888, 986]
```
隨著 n 不斷地增長，我們只需要在長度為 n-2 的中心對稱數兩邊添加 11，69，88，96 即可。
**代碼實現**
```
List<String>?helper(int?n,?int?m)?{
????//?第一步：判斷輸入或者狀態是否非法？
????if?(n?<?0?||?m?<?0?||?n?>?m)?{
????????throw?new?IllegalArgumentException("invalid?input");
??}
????//?第二步：判讀遞歸是否應當結束?
????if?(n?==?0)?return?new?ArrayList<String>(Arrays.asList(""));
????if?(n?==?1)?return?new?ArrayList<String>(Arrays.asList("0",?"1",?"8"));
??
????//?第三步：縮小問題規模
????List<String>?list?=?helper(n?-?2,?m);?
????//?第四步:?整合結果
????List<String>?res?=?new?ArrayList<String>();
??
????for?(int?i?=?0;?i?<?list.size();?i++)?{
????????String?s?=?list.get(i);
????
????????if?(n?!=?m)?res.add("0"?+?s?+?"0");
????
????????res.add("1"?+?s?+?"1");
????????res.add("6"?+?s?+?"9");
????????res.add("8"?+?s?+?"8");
????????res.add("9"?+?s?+?"6");
????}
??
????return?res;
}
```
**算法分析**
分析非遞歸算法的時間復雜度非常直接，例如，前一節課里分析過冒泡排序以及插入排序的時間復雜度，分析方法就是數有多少層循環，由于每層循環里面執行的操作都是對比和交換，時間復雜度是 O(1)，所以，最終的時間復雜度就是將每層循環的長度相乘。
分析遞歸算法推薦兩種方法：
* 迭代法
* 公式法
* [ ] 迭代法
舉例：分析漢諾塔遞歸函數的時間復雜度。
```
void?hano(char?A,?char?B,?char?C,?int?n)?{
????if?(n?>?0)?{
????????hano(A,?C,?B,?n?-?1);
????????move(A,?C);
????????hano(B,?A,?C,?n?-?1);
????}
}
```
假設這個遞歸函數的運行時間是 T(n)。
1. if 語句（一般取 if 塊或 else 塊之間最大的時間復雜度）中，比較和判斷 n 的大小，CPU 的執行時間為 1 個單位。
2. 兩次調用遞歸函數，每次都使問題的規模減少 1 個，得到兩倍的 T(n-1)。打印輸出的語句，CPU 的執行時間也為 1 個單位。因此得出：T(n) = 1 + 2×T(n - 1) + 1。
此處 if 語句和打印輸出語句的執行時間與問題規模 n 無關，因此它們的算法時間復雜度可以記為 O(1)，表達式變為：T(n) = 2×T(n - 1) + O(1)。
當 n=0 的時候，T(0) = 1，因為當沒有盤子的時候，if 語句也要進行一次比較，判斷 n 是否大于 0。
3. 用迭代法將 T(n) 進行展開。
T(n - 1) = 2×T(n - 2) + 1，以此類推，不斷地代入到 T(n) 的表達式當中，得到如下關系：
```
T(n) = 2× (2×T(n - 2) + 1) + 1 = 22×T(n - 2) + (2 + 1)
T(n) = 2×(2× (2×T(n - 3) + 1) + 1) + 1 = 23×T(n - 3) + (4 + 2 + 1)
T(n) = 2×(2×(2×(2×T(n - 4) + 1) + 1) + 1) + 1 = 24×T(n - 4) + (8 + 4 + 2 + 1)
…
T(n) = 2k×T(n - k) + (2k?- 1)
```
其中，1 + 2 + 4 + 8 + … 是一個等比數列，由求和公式得到 2k?- 1。當 k 等于 n 的時候，T(n) = 2n×T(0) + (2n?- 1)，由于 T(0) 等于 1，所以最終 T(n) = 2×2n?- 1。
對 T(n) 求 O 的值得到：O(n) = O(T(n)) = O(2×2n?- 1) ，忽略掉常量和系數，O(n) = O(2n)。
所以，整個算法的時間復雜度就是 O(2n)。
而很難通過迭代法推導出比較復雜的時間復雜度的時候，可以借用公式法。
* [ ] 公式法
公式法可以說是計算遞歸函數復雜度最方便的工具，當遞歸函數的時間執行函數滿足如下的關系式時，我們可以利用公式法：T(n) = a×T(n/b) + f(n)。
其中，f(n) 是每次遞歸完畢之后額外的計算執行時間。例如，在歸并排序中，每次遞歸處理完兩邊的數組后，我們需要執行合并的操作，那么這個操作的執行時間就是 f(n)。
當參數 a、b 都確定的時候，光看遞歸的部分，它的時間復雜度就是：O(n^logba)。
由于時間復雜度求的是上界（upper bound)，通過對比遞歸部分的時間復雜度和 f(n) 的大小關系，得出最后的整體時間復雜度。牢記以下三種情況和相應公式：
1. 當遞歸部分的執行時間 nlog(b)a 大于 f(n) 的時候，最終的時間復雜度就是?O(n^logba)。
2. 當遞歸部分的執行時間 nlog(b)a 小于 f(n) 的時候，最終的時間復雜度就是 f(n)。
3. 當遞歸部分的執行時間 nlog(b)a 等于 f(n) 的時候，最終的時間復雜度就是?O(n^logba)logn。
* 舉例 1：分析歸并排序的時間復雜度。
```
T(n) = 2T(n/2) + n
a = 2，b = 2，f(n) = n
logba = 1，n1?= n
```
符合第三種情況，最終的時間復雜度就是 O(nlogn)。
* 舉例 2：分析下面函數的時間復雜度。
```
int?recursiveFn(int?n)?{
????if?(n?==?0)?{
????????return?0;
????}
????return?recursiveFn(n?/?4)?+?recursiveFn(n?/?4);
}
```
得出時間執行函數：T(n) =? 2×T(n/4) + 1，a = 2，b = 4，f(n) = 1。
代入公式得到：n^log42 = n0.5，當 n>1 的時候，n0.5>1，因此，時間復雜度就是 ?O(n0.5)。
* 舉例 3：已知時間執行函數如下，分析時間復雜度。
```
T(n) = 3×T(n/2) + n2
a = 3，b = 2，f(n) = n2
```
最復雜的操作發生在遞歸完成之后，符合第二種情況。
代入公式得到：n^log23 = n1.48<n2，最后遞歸的時間復雜度是 O(n2)。
* [ ] 小結
對于時間復雜度的分析是算法面試中非常重要的一環，掌握好迭代法和公式法，對于分析大多數面試題都有非常重要的幫助，需要通過不斷地練習，來熟練運用它們。
* [ ] 回溯（Backtracking）
* 算法思想
回溯實際上是一種試探算法，這種算法跟暴力搜索最大的不同在于，在回溯算法里，是一步一步地小心翼翼地進行向前試探，會對每一步探測到的情況進行評估，如果當前的情況已經無法滿足要求，那么就沒有必要繼續進行下去，也就是說，它可以幫助我們避免走很多的彎路。
回溯算法的特點在于，當出現非法的情況時，算法可以回退到之前的情景，可以是返回一步，有時候甚至可以返回多步，然后再去嘗試別的路徑和辦法。這也就意味著，想要采用回溯算法，就必須保證，每次都有多種嘗試的可能。
* [ ] 解題模板
* 解題步驟
1. 判斷當前情況是否非法，如果非法就立即返回；
2. 當前情況是否已經滿足遞歸結束條件，如果是就將當前結果保存起來并返回；
3. 當前情況下，遍歷所有可能出現的情況并進行下一步的嘗試；
4. 遞歸完畢后，立即回溯，回溯的方法就是取消前一步進行的嘗試。
代碼模板
```
function?fn(n)?{
????//?第一步：判斷輸入或者狀態是否非法？
????if?(input/state?is?invalid)?{
????????return;
??}
????//?第二步：判讀遞歸是否應當結束?
????if?(match?condition)?{
????????return?some?value;
??}
????//?遍歷所有可能出現的情況
????for?(all?possible?cases)?{
??
????????//?第三步:?嘗試下一步的可能性
????????solution.push(case)
????????//?遞歸
????????result?=?fn(m)
????????//?第四步：回溯到上一步
????????solution.pop(case)
????
????}
????
}
```
* [ ] 例題分析一
LeetCode 第 39 題：給定一個無重復元素的數組?candidates?和一個目標數?target?，找出?candidates?中所有可以使數字和為?target?的組合。candidates?中的數字可以無限制重復被選取。
說明：
* 所有數字（包括?target）都是正整數。
* 解集不能包含重復的組合。?
**解題思路**
題目要求的是所有不重復的子集，而且子集里的元素的值的總和等于一個給定的目標。
* [ ] 思路 1：暴力法。
羅列出所有的子集組合，然后逐個判斷它們的總和是否為給定的目標值。解法非常慢。
* [ ] 思路 2：回溯法。
1. 從一個空的集合開始，小心翼翼地往里面添加元素。
2. 每次添加，檢查一下當前的總和是否等于給定的目標。
3. 如果總和已經超出了目標，說明沒有必要再嘗試其他的元素了，返回并嘗試其他的元素；
4. 如果總和等于目標，就把當前的組合添加到結果當中，表明我們找到了一種滿足要求的組合，同時返回，并試圖尋找其他的集合。
代碼實現
```
int[][]?combinationSum(int[]?candidates,?int?target)?{
????int[][]?results;
????backtracking(candidates,?target,?0,?[],?results?-?換另外一種顏色高亮);
????return?results;
}
void?backtracking?=?(int[]?candidates,?int?target,?int?start,?int[]?solution,?int[][]?results)?=>?{
????if?(target?<?0)?{
????????return;
??}
????if?(target?===?0)?{
????????results.push(solution);
????????return;
??}
????for?(int?i?=?start;?i?<?candidates.length;?i++)?{
????????solution.push(candidates[i]);
????????backtracking(candidates,?target?-?candidates[i],?i,?solution,?results);
????????solution.pop();
????
????}
??
}
```
在主函數里：
1. 定義一個 results 數組用來保存最終的結果；
2. 調用函數 backtracking，并將初始的情況以及 results 傳遞進去，這里的初始情況就是從第一個元素開始嘗試，而且初始的子集為空。
在 backtracking 函數里：
1. 檢查當前的元素總和是否已經超出了目標給定的值，每添加進一個新的元素時，就將它從目標總和中減去；
2. 如果總和已經超出了目標給定值，就立即返回，去嘗試其他的數值；
3. 如果總和剛好等于目標值，就把當前的子集添加到結果中。
在循環體內：
1. 每次添加了一個新的元素，立即遞歸調用 backtracking，看是否找到了合適的子集
2. 遞歸完畢后，要把上次嘗試的元素從子集里刪除，這是最重要的。
以上，就完成了回溯。
提示：這是一個最經典的回溯的題目，麻雀雖小，但五臟俱全。它完整地體現了回溯算法的各個階段。
* [ ] 例題分析二
LeetCode 第 51 題， 在一個 N×N 的國際象棋棋盤上放置 N 個皇后，每行一個并使她們不能互相攻擊。給定一個整數 N，返回 N 皇后不同的的解決方案的數量。
* 解題思路
解決 N 皇后問題的關鍵就是如何判斷當前各個皇后的擺放是否合法。
利用一個數組 columns[] 來記錄每一行里皇后所在的列。例如，第一行的皇后如果放置在第 5 列的位置上，那么 columns[0] = 6。從第一行開始放置皇后，每行只放置一個，假設之前的擺放都不會產生沖突，現在將皇后放在第 row 行第 col 列上，檢查一下這樣的擺放是否合理。
方法就是沿著兩個方向檢查是否存在沖突就可以了。
* 代碼實現
首先，從第一行開始直到第 row 行的前一行為止，看那一行所放置的皇后是否在 col 列上，或者是不是在它的對角線上，代碼如下。
```
boolean?check(int?row,?int?col,?int[]?columns)?{
????for?(int?r?=?0;?r?<?row;?r++)?{
????????if?(columns[r]?==?col?||?row?-?r?==?Math.abs(columns[r]?-?col))?{
????????????return?false;
????????}
????}
????return?true;
}
```
然后進行回溯的操作，代碼如下。
```
int?count;
int?totalNQueens(int?n)?{
????count?=?0;
????backtracking(n,?0,?new?int[n]);
????return?count;
}
void?backtracking(int?n,?int?row,?int[]?columns)?{
????//?是否在所有n行里都擺放好了皇后？
????if?(row?==?n)?{
????????count++;?//?找到了新的擺放方法
????????return;
??}
????//?嘗試著將皇后放置在當前行中的每一列???
????for?(int?col?=?0;?col?<?n;?col++)?{
????????columns[row]?=?col;
????????//?檢查是否合法，如果合法就繼續到下一行
????????if?(check(row,?col,?columns))?{
????????????backtracking(n,?row?+?1,?columns);
????????}
????????//?如果不合法，就不要把皇后放在這列中（回溯）
????????columns[row]?=?-1;
????}
}
```
**算法分析**
回溯其實是用遞歸實現的，因此我們在分析回溯的時間復雜度時，其實就是在對遞歸函數進行分析，方法和之前介紹的一樣。
舉例：分析一下 N 皇后的時間復雜度。
假設 backtracking 函數的執行時間是 T(n)。
解法：
1. 每次都必須遍歷所有的列，一共有 n 列。
2. 在每次遍歷中，先要利用 check 函數檢查當前的擺放方法會不會產生沖突，檢查的時間復雜度由當前所在的行決定，上限是 n，所以總時間復雜度就是?O(n2)。
3. 遞歸地嘗試著每種擺放，當我們放好了第一個皇后，剩下要處理的之后 n-1 個皇后，問題的規模減少了一個，于是執行時間變成了 T(n - 1)。
最終得到了 T(n) 的表達式：T(n) = n×T(n - 1) +?O(n2)。
利用迭代法將 T(n) 展開得到：
```
T(n) = n×((n - 1)×T(n - 2) +??(n - 1)2?+?n2
…
T(n) = n×(n - 1)×(n - 2)× … ×1 + 1 + 22?+ 32?+ … (n - 1)2?+ n2
```
前面一部分是階乘，后面一部分是平方求和，根據公式最后得到：
```
T(n) = n! + n(n+1)(2n+1)/6
O(T(n)) = n! + O(n3)
```
由于 n!>n3，因此，它的上界就是 n!，即：O(T(n)) = n!
* [ ] 結語
遞歸和回溯可以說是算法面試中最重要的算法考察點之一，很多其他算法都有它們的影子。例如，二叉樹的定義和遍歷就利用到了遞歸的性質；歸并排序、快速排序的時候也運用了遞歸；我們將在第 6 課介紹動態規劃，它其實是對遞歸的一種優化；還有第 7 課里的二分搜索，也可以利用遞歸去實現。
注意：要能熟練掌握好分析遞歸復雜度的方法，必須得有比較扎實的數學基礎，比如對等差數列、等比數列等求和公式要牢記。
建議：LeetCode 上對遞歸和回溯的題目分類做得很好，有豐富的題庫，建議大家多做。
