一次看懂遞迴 (Recursion) 的思維模式（四）
排列組合（Permutation & Combination)
這章要與大家介紹兩個經典數學概念：組合（Combination）與排列（Permutation）。這也是回溯法（Backtracking） 技巧的常見應用之一，更是演算法考題的重點基礎項目，如果遞迴的基礎還不夠好，或對回溯法很陌生的朋友，建議先看上一篇。
雖然是數學題目，但其實這篇完全不會提到數學，我們著重的點在於如何寫程式來把所有可能性給列出來。就讓我們開始吧！
組合 （Combination）
Combination 類型的最基本問題，就是我們想知道在給定條件下，可以有幾種不同的組合。只要內容物不同，就被我們當作不同的組合，但如果內容物相同，只有排序不同，我們仍然視為相同組合。例如 [1, 2, 3] 與 [1, 2, 5] 是不同的組合，但 [1, 2, 3] 與 [3, 2, 1] 則被視為相同的組合，以下是來看看實際題目：
給定元素 [1, 2, 3, 4]，想從中挑選 3 個，不能重複挑選，請列出所有可能組合
先讓我們自己觀察一下，應該不難看出，答案只有四種，如下：
[1, 2, 3], [1, 2, 4], [1, 3, 4], [2, 3, 4]
但我們怎樣寫一個程式來找到他們呢？來看看上一篇學過的技巧怎樣派上用場。
- 第零層，一樣我們從空無一物開始，但這次我們旁邊多註記了一下我們所有還可以使用的元素，這個非常重要，接下來我們就會使用它
2. 第一層，中間的答案是空的，還可以用的元素當然是全部的 [1, 2, 3, 4]。我們一樣將所有可以的元素放進去，並同樣在旁邊記錄還可以使用的元素。注意一個細節，由於 Combination 的特性是不同的順序視為一樣，例如 [1,2] 與 [2,1] 是一樣的，所以為了避免這種重複出現，我們僅保留順序排在選取元素後面的元素們，留給後續使用。所以第一層會變成如以下：
如上圖所示，如果選了第一個元素 [1]，則後面三個元素，都還繼續被當成可以使用的元素，如果選了第二個元素 [2]，則只有後面的 [3, 4] 被視為可以使用的元素，[1] 則不再使用，避免掉重複問題。
另外可以發現，當選擇第四個元素時，此分支的還可以使用的元素就會變空的，這種分枝接下來將不會再繼續遞迴下去，產生新分支了，而是直接回溯（Backtracking）回去。
3. 接下來進入第二層，相同的規則繼續往下
到這一層，會發現有更多分枝的可以使用的元素已經清空了。提早停掉這些分支繼續往下擴大，可以大幅增加演算法的效率。這些提早的停止分支的動作也稱爲剪枝（Pruning）。
4. 最後，來到我們的第三層
一旦某個分支的內容物已經達到指定個數（3個），他也將會停止繼續搜索，記錄答案後就回溯（Backtracking）回去。如我們最左下角的分支，他雖然還有可用元素，但也會停止在這邊。如此，我們原本預設的四個答案都在最後一層出現啦！以下來看看程式該怎麼寫：
- start：記錄目前走到哪個 index，我們只能用從它開始以後的元素繼續遞迴下去搜索（靠他可以得到上圖中，方框右側的東西）
- comb：記錄目前可能答案（代表的就是上圖中，方框內部的東西）
- nums：原本全部可用元素陣列，以上面例子來說就是 [1, 2, 3, 4]
- max_length：最終答案陣列的長度，以上面例子來說就是 3
def find(start, nums, max_length, comb):
if len(comb) == max_length:
print(comb)
return for i in range(start, len(nums)):
comb.append(nums[i])
find(i + 1, nums, max_length, comb)
comb.pop()find(0, [1, 2, 3, 4], 3, [])
套用這個概念，我們就能來解 Leetcode 77 Combinations 的問題，題目是給定一個 n，代表可以使用的元素是 1~n，另外給定一個 k，代表最終答案想要取幾個元素，下面為範例程式碼。
如果有仔細看範例程式碼，會發現最前面多了個沒提到的神祕判斷
if len(comb) + (len(nums) - start) < max_length:
return這句是當我們發現剩下的元素就算全部用完，也一定達不到要求的答案長度時，可以提早退出，這可以讓我們的程式碼再加速不少（但你不用他也可以被 Accept）。如果以時間複雜度來分析的話，假如我們都不做任何的提前結束優化，則總時間複雜度會是 O(2^N)，但如果把所有的優化都做到最好，則時間複雜度就是總排列個數，也就是 O(C(N, K))，其中 C(N, K) 就是高中數學學過的二項式係數。
雖然已經完成了，但我想和大家介紹另一個稍微不同的思路，一樣可以解決 Combination 的問題。上面的做法中，我們每次都把所有可能的元素嘗試一遍，但有另一個想法，是我們依序針對每個元素，每次都依照”選擇此元素”與”不選擇此元素”，走出兩個分支，如下所示：
- 第零層到第一層時：我們開啟兩個分支，使用元素 1 與不使用元素 1。
2. 第一層到第二層，則是繼續遞迴開啟兩個分支，使用元素 2與不使用元素 2。
3. 第二層到第三層的時候，會發現已經有分支找到 3 個元素了，這個分支就會在這邊停下來，如下圖紅框框所示
4. 最後一層，將最後一個元素也用上，並得到全部答案，如下
同樣貼上範例程式碼給大家看看。
用這個思路可以更好的理解，為何如果不做任何提前結束的優化，總時間複雜度會變成 O(2^N)，因為對於每個元素，我們都要展開兩個分支。但只要有適當的將不可能的分支都提早結束掉，最終時間複雜度也會與第一個方法一致。
最後，帶大家看一下另一個相似的題目
排列 （Permutation）
Permutation 類型的最基本問題，就是我們想知道在給定條件下，可以有幾種不同的排列。與 Combination 唯一差異，就是不同的順序，也被我們視為不同排列。看以下實際例子
給定元素 [1, 2, 3]，從中挑選 3 個，不能重複挑選，請列出所有可能排列
同樣我們先自己觀察一下，答案只有六種，如下：
[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]
做法與 Combination 其實非常相似，只是這次，我們每一輪的元素都是 [1, 2, 3]，但由於不能重複使用，所以要排除掉已經出現過的元素。這部分我們採用 Set 來記錄已經使用過得元素，因為這個資料結構可以在 O(1) 的時間複雜度內新增、刪除、查詢元素。在下圖中用大括號 { } 來代表 Set 中的元素。
所以在每一層，我們都會依序詢問 1, 2, 3 是否曾經出現在 {…} 裡面，只要沒出現，就把元素加入 Permutation Array，並在 Set 中同時記錄此元素已經出現過，然後往下遞迴下一層。
PS：Set 是一個不保證排序的資料結構，只能知道裡面有哪些元素。
以下用 Leetcode 46 Permutation 來寫範例程式碼
本章到此結束。如果到目前都還有看懂的讀者，恭喜你，對遞迴應該已經有滿好的理解了。同樣的概念可以應用在 Leetcode 上面的 Combination Sum 與 Subset 的系列題組上，就留給讀者自己挑戰看看，拿上面的 code 改幾行就可以過了，是非常好的考驗自己是否學會的題組。
不過遞迴的故事還沒完全結束。窮舉所有的可能性雖然很棒，但時間複雜度也非常高，幾乎是指數級別，有時題目或許不需要我們真的把答案都窮舉出來，那我們就該尋找更高效的做法。另外，有時候我們在把大問題切小的時候，小問題也可能不停的重複出現（想想費氏數列），導致遞迴時浪費一堆時間重複計算。如果想知道這些問題的解法，請看下一章 — 動態規劃。
