作者 | 碼海
責編 | Elle
前言
上一篇「一文學會遞歸解題」一文頗受大家好評，各大號紛紛轉載，讓筆者頗感欣慰，不過筆者注意到後臺有讀者有如下反饋
確實，相信很多人（包括我自己）都有類似的感慨，對某個知識點，看確實是看懂了，但如果真的再用同樣的套路再去解一些帶有同樣解題思路，但稍加變形的題，往往會束手無策。對這種情況有啥好的解決辦法嗎？
除了勤加練習，還有一良策！
魯迅先生說：如果學習算法，最好一段時間內只刷某種算法思想或某種數據結構的題，啥意思呢?比如說你上次學了遞歸，那就持續找遞歸的題來刷，學了鍊表，這段時間就專門刷鍊表的題，千萬不可今天刷遞歸，明天刷動態規劃，後天又開始學習貪心算法。。。新手最怕的就是以為自己懂了，淺嘗輒止，這是新手的大忌！一定要對同一類型的題窮追猛打，形成肌肉記憶，這樣之後再碰到同一類型的題就會條件反射地一看:哦,這題用 xxx 思想應該可以靠譜。
言歸正轉，排列組合是面試中的熱門考點因為看似簡單的排列組合可以有挺多的變形，根據變形，難度可以逐漸遞增，而且排列組合本身有挺多的解法，能很好地區分一個侯選者的算法水平，排列組合如果用遞歸挺不容易理解的（反正筆者一開始看了好幾遍代碼愣是沒看懂），之後我會教大家如何用一種非常簡單地方式來理解排列組合的遞歸，這也是寫本文的根本目的
接下來我們看看如何用 「遞歸四步曲」來解排列組合,本文會從以下幾個方面來講解排列組合
什麼是排列排列的常用解法什麼是組合組合遞歸解法面試中排列組合的一些變形
什麼是排列
排列的定義：從n個不同元素中，任取 m (m≤n,m與n均為自然數,下同）個不同的元素按照一定的順序排成一列，叫做從n個不同元素中取出m個元素的一個排列；從n個不同元素中取出m(m≤n）個元素的所有排列的個數，叫做從n個不同元素中取出m個元素的排列數，當 n = m 時，我們稱這樣的排列為全排列
看到這個公式，大家是不是回憶起了高中的排列公式啦
我們重新溫習一下，以 1, 2, 3 這三個數字的全排列有多少種呢。
第一位我們可以選擇 3 個數字，由於第二位不能與第一位相等，所以第二位只能選 2 個數字，第一，第二位既然選完了，那麼第三位就只有 1 個數字可選了，所以總共有 3 x 2 x 1 = 6 種排列。
既然知道了什麼是全排列，那我們來看看怎麼用程序來列印全排列的所有情況：求 數字 1 到 n (n < 10) 的全排列
排列的常用解法
這道題如果暫時沒什麼頭緒，我們看看能否用最簡單的方式來實現全排列，什麼是最簡單的方式，暴力窮舉法!
暴力窮舉法
大家仔細看上文中 1，2 ，3 的全排列，就是把所有情況全部列舉出來了，所以我們用暴力窮舉法怎麼解呢,對每一位的每種情況都遍歷出來組成所有的排列，再剔除重複的排列，就是我們要的全排列了
/** * 求數字第 1 到 n 的全排列 */publicvoidpermutation(int n) {for(int i = 1; i < n + 1; i ++) {for(int j = 1; j < n + 1; j ++) {for(int k = 1; k < n + 1; k ++) {if (i != j && i != k && j != k) { System.out.println(i + j + k); } } } }}
時間複雜度是多少呢,做了三次循環，很顯然是
很多人一看時間複雜度這麼高，多數都會嗤之以鼻，但是要我說，得看場景，就這題來說用暴力窮舉法完全沒問題，n 最大才 9 啊，總共也才循環了 9^3 = 729 次,這對現在的計算機性能來說簡單不值一提，就這種場景來說，其實用暴力窮舉法完全可行!
這裡說句題外話，我們在學習的過程中一定要視場景選擇合適的技術方案，有句話說：過早的性能優化是萬惡之源，說的就是這個道理，這就好比，一個初創公司，dau 不過千，卻要搞分布式，中間件，一個 mysql 表，記錄不過一萬，卻要搞分庫分表。。。這就鬧笑話了，記住沒有最牛逼的技術，只有最合適的技術！能解決當前實際問題的技術，就是好技術！
遞歸解題
這是筆者寫此文的根本目的！就是為了講清楚怎麼用遞歸來更好地理解排列組合！因為我發現很多網友都覺得排列組合的遞歸解法實在不能 Get 到點上， 當初筆者也是看了好幾遍代碼才勉強理解，不過過了一段時間再看又忘了,後來根據筆者悟出的一套遞歸四步曲來理解，容易多了，現與各位分享！仔細看好啦
我們先來觀察一下規律，看下怎樣才能找出排列是否符合遞歸的條件，因為如前文 所述，必須要找出題目是否能用遞歸才能再用遞歸四步曲來解題
乍一看確實看不出什麼所以然出來，那我們假設第一個數字已經選中了（假定為1），問題是不是轉化為只求後面三位數的全排列了，發現沒有，此時全排列從前面 n 位數的全排列轉化成了求之後 n-1 位數的全排列了,問題從 n 變成了 n-1，規模變小了！而且變小的子問題與原問題具有相同的解決思路,都是從求某位開始的全排列！符合遞歸的條件！
既然我們發現排列符合遞歸條件，那我們就可以用遞歸四步曲來解了
1、定義函數的功能要求數字 1 到 n 的全排列，我們定義以下函數的功能為求從 k 位開始的全排列,數組 arr 存的是參與全排列的 1 到 n 這些數字
publicvoidpermutation(int arr[], k){}
2、尋找遞推公式注意上面形成遞歸的條件：第一個數字已經選中了！那第一位被選中有哪些情況呢,顯然有以下幾種情況
即在第一位上把所有的數字都選一遍，怎麼做才能把所有的數字都在第一位上都選一遍呢，把第一位與其他 n-1 位數分別交換即可（注意每一次交換前都要保證是原始順序），如下
畫外音：第一步交換自己其實就是保持不變，因為我們要保證在第一位所有數字都能取到，如果移除了這一步，則第一位少了數字 1 ，全排列就漏了
這樣我們就把第一位的所有數字都選了遍，之後只要對剩餘的 n-1 位數做全排列即可（即調用第一步的函數），切忌再對 n-1 再做展開,只要我們發現遞推關係就行了，千萬不要陷入層層展開子問題的陷阱當中去！注意要從函數的功能來理解，因為問題與子問題具有相同的解決思路，所以第 1 步定義的函數對子問題（求 n-1 ,n-2 ... 的全排列）同樣適用!
那遞歸的終止條件是什麼呢 ，顯然是從 n 縮小到對最後一位的全排列(此時 k 指向 arr 的最後一個元素)
於是我們可以得出遞推關係為:permutation(int arr[], k) = 選中第k位（將第k位與之後的 n- k 位分別交換） + permutation(int arr[], k+1)
3、將第二步的遞推公式用代碼表示出來補充到步驟 1 定義的函數中，補充後的函數如下
/** * * @param arr 代表全排列數字組成的數組 * @param k 代表第幾位 */publicvoidpermutation(int[] arr, int k) {// 當 k 指向最後一個元素時,遞歸終止，列印此時的排列排列if (k == arr.length - 1) { System.out.println(Arrays.toString(arr)); } else {for (int i = k; i < arr.length; i++) {// 將 k 與之後的元素 i 依次交換,然後可以認為選中了第 k 位 swap(arr, k, i);// 第 k 位選擇完成後，求剩餘元素的全排列 permutation(arr, k+1);// 這一步很關鍵：將 k 與 i 換回來，保證是初始的順序 swap(arr, k, i); } }}publicstaticvoidswap (int[] arr, int i, int j) {int t = arr[i]; arr[i] = arr[j]; arr[j] = t;}
我看網上有不少人對最後一步（如圖示）不理解
回過頭去看上面的遞歸過程圖中我們特意強調了注意每一次交換時都要保證是原始順序所以最後一個 swap 要做的事情就是每次交換第一個數字與後面被選中的那個數，做完之後元素的全排列之後，要把數字交換回來，以保證接下來再用第一位與其他位的數字進行交換前是原始的序列，這樣才能保證第一位數字與之後的 n-1 個元素依次交換之後都是不重複的。
註定一定要從函數的功能去理解遞歸，全排列的函數從功能上可以這麼理解，選中第 k 位 + 計算之後的 n-k 位的全排序， 而且由於是遞歸，之後的 n-k 位也可以重複調用同樣的函數持續求解！
4、求時間/空間複雜度由於我們只用了一個數組 arr，所以空間複雜度顯然是 O(n)，那時間複雜度呢，仔細看上面的編碼可以很明顯地看出計算 n 的全排列需要做 n 次循環，循環裡是要做 2 次交換（由於是固定數字，可以認為是常數 C ），還有一次對之後 n-1 次元素的全排列所以 f(n) = n * (C + f(n-1))，C是常數可以忽略,所以
f(n) = n * f(n-1) = n * (n-1) * f(n-2) = n!,所以時間複雜度是 O(n!)，注意不可能有比這個更好的時間複雜度了！因為全排列的組合本身就有 n! 次，再怎麼優化都肯定會有這麼多次
在 n 較大的情況下顯然是不可接受的，所以我們要想辦法進行優化
字典序法
除了遞歸解法，還有一種常用的解法：字典排序法啥叫字典排序法？
舉個例子：1 2 3 這三位數字的全排列如下
1 2 3 ， 1 3 2 ， 2 1 3 ， 2 3 1 ， 3 1 2 ， 3 2 1
以上排列滿足從小到大依次遞增，按這種方式排列的算法就叫字典排序法。
所以我們只要從排列的最小值開始,依次按從小到大依次遞增的順序找尋下一個全排列的數字即可，直到最大值！就能找到所有全排列。
假設我們定義了一個叫 nextPermutation 的函數,根據字典排序法，則從最小值 123 開始，持續調用這個函數即可求出所有全排列的組合,如圖示
那麼這個函數該怎麼實現呢
有 4 個步驟
1、從右到左（從個位數往高位數）尋找第一個左鄰小於右鄰的數，如果找不到說明此時的數字為全排列的最大值
2、再從右往左找第一個比第一步找出的數更大的數
3、交換上面兩個步驟中的數
4、假設第一步尋找的數對應的位置為 i，則將 i+1至最後一個元素從小到大進行排序，排好序後，此時的數字就是我們要找的那個排列
舉個例子: 假設當前給的數字是 124653， 按這四個步驟來看如何尋找這個數按字典排序法的下一個全排列數字
1、從右到左（從個位數往高位數）尋找第一個左鄰小於右鄰的數，顯然是 4
124653
2、再從右往左找第一個比第一步找出的數（4）更大的數, 顯然是 5
124653
3、交換上面兩個步驟中的數,即交換 4， 5，此時數字為 125643
4、 125643 中的 643 從小到大進行排序，顯然應該為 125346,這一步的排序我們用了快排
整體思路還是很清晰的，如果不太清楚，建議大家多看幾遍。
思路清楚了，代碼寫起來就快了，直接貼上按以上步驟來實現的代碼吧，注釋寫得很詳細了，大家可以對照著看
/** * * @param arr 當前排列 * @return boolean 如果還有下一個全排列數，則返回 true, 否則返回 false */publicbooleannext_permutation(int[] arr){int beforeIndex = 0; //記錄從右到左尋找第一個左鄰小於右鄰的數對應的索引int currentIndex;boolean isAllReverse = true; // 是否存在從右到左第一個左鄰小於右鄰的數對應的索引// 1. 從右到左（從個位數往高位數）尋找第一個左鄰小於右鄰的數for(currentIndex = arr.length - 1; currentIndex > 0; --currentIndex){ beforeIndex = currentIndex - 1;if(arr[beforeIndex] < arr[currentIndex]){ isAllReverse = false;break; } }//如果不存在，說明這個數已經是字典排序法裡的最大值，此時已經找到所有的全排列了,直接列印即可if(isAllReverse){returnfalse; } else {// 2. 再從右往左找第一個比第一步找出的數更大的數的索引int firstLargeIndex = 0;for(firstLargeIndex = arr.length - 1; firstLargeIndex > beforeIndex; --firstLargeIndex) {if (arr[firstLargeIndex] > arr[beforeIndex]) {break; } }// 3. 交換 上述 1, 2 兩個步驟中得出的兩個數 swap(arr, beforeIndex, firstLargeIndex);// 4. 對 beforeIndex 之後的數進行排序，這裡用了快排 quicksort(arr, beforeIndex + 1, arr.length);returntrue; }}publicvoidswap(int[] arr, int i, int j){int t = arr[i]; arr[i] = arr[j]; arr[j] = t;}
註：以上第四步的排序用到了快排（quicksort），限於篇幅關係沒有貼出快排的完整代碼，如果不了解快排，建議大家網上查查看，這裡不做詳細展開
那 next_permutation 的時間複雜度是多少呢，從以上的步驟中其實可以看到是第四步做快排時的時間複雜度，即 O(nlogn)。
next_permutation 我們寫好了，接下來要尋找全排列就容易了，思路如下
1、 首先對參與全排列的數字數組作排序，保證初始的排列數字一定是最小的即如果起始的 int[] arr = {4,3,2,1} 經過快排後會變成 {1,2,3,4}
2、持續調用定義好的 next_permutation 函數，直到最大值
publicvoidpermutation(int[] arr){// 1、 快排，保證 arr 裡的元素是從小到大的 quicksort(arr);// 2、持續調用定義好的 next_permutation 函數，直到最大值while(next_permutation(arr)) { System.out.println(Arrays.toString(array)); }}
可以看到如果定義好了 next_permutation，在算全排列還是很簡單的，那用字典序法的時間和空間複雜度是多少呢由於全程只用了arr 數組，空間複雜度顯示是 O(n)而時間複雜度顯然是第一步快排的空間複雜度 + 持續做 next_permutation 計算的時間複雜度。
快排的時間複雜度為 O(nlogn)，而 next_permutation 由於要計算 n! 次， 且根據以上分析我們已經知道了 next_permutation 的時間複雜度是 O(nlogn), 所以整體的時間複雜度是
O(nlog) + O(n! * nlogn) = O(n! * nlogn)。
看起來字典序法比遞歸的時間複雜度更高,所以我們應該使用傾向於使用遞歸嗎？這裡注意: 遞歸的實現是通過調用函數本身，函數調用的時候，每次調用時要做地址保存，參數傳遞等，這是通過一個遞歸工作棧實現的。具體是每次調用函數本身要保存的內容包括：局部變量、形參、調用函數地址、返回值。那麼，如果遞歸調用N次，就要分配N局部變量、N形參、N調用函數地址、N返回值，這勢必是影響效率的，同時，這也是內存溢出的原因，因為積累了大量的中間變量無法釋放。
所以在時間複雜度差不多的情況下，優化選擇非遞歸的實現方式
什麼是組合
看完了排列，我們來看看組合，首先我們還是先看看組合的定義
組合（combination）是一個數學名詞。一般地，從n個不同的元素中，任取m（m≤n）個元素為一組，叫作從n個不同元素中取出m個元素的一個組合。我們把有關求組合的個數的問題叫作組合問題。
假設有數字1, 2, 3, 4, 要從中選擇 2 個元素，共有多少種組合呢
共有 6 種
排列與組合最主要的區別就是排列是有序的，而組合是無序的，12 和 21 對組合來說是一樣的
現在我們來看看如果從 n 個元素中選出 m 的組合共有幾種，之前詳細地講解了如何用遞歸解排列，相信大家應該對組合怎麼使用遞歸應該有一個比較清晰的思路。
我們一起來看看，假設要從 n 選 m 的組合的解題思路
這裡需要注意的是相對於全排列的每個元素都能參與排列不同，組合中的每個元素有兩種狀態，選中或未選中,所以形成遞歸分兩種情況。
如果第一個元素選中，則要從之後的 n-1 個元素中選擇 m-1 個元素
如果第一個元素未被選中，則需要從之後的 n-1 個元素選擇 m 個元素
遞歸條件既然找到了，接下來我們就按遞歸四步曲來解下組合。
1、定義函數的功能定義以下函數為從數組 arr 中第 k 個位置開始取 m 個元素（如下的 COMBINATION_CNT）
public static final int COMBINATION_CNT = 5; // 組合中需要被選中的個數public static void combination(int[] arr, int k, int[] select) {}
這裡我們額外引入了一個 select 數組，這個數組裡的元素如果為1，則代表相應位置的元素被選中了，如果為 0 代表未選中
如圖示，以上表示 arr 的第 2，3 元素被選中作為組合
2、尋找遞推公式顯然遞推公式為
combination(arr, k,m) = (選中 k 位置的元素 +combination(arr, k+1) ) + (不選中 k 位置的元素 +combination(arr, k+1) )
那麼終止條件呢，有兩個
一個是被選中的元素已經等於我們要選擇的組合個數了一個是 k （開始選取的數組索引） 超出數組範圍了。3、將第二步的遞推公式用代碼表示出來補充到步驟 1 定義的函數中，補充後的函數如下
publicstatic final int COMBINATION_CNT = 5; // 組合中需要被選中的個數publicstaticvoidcombination(int[] arr, int k, int[] select) {// 終止條件1：開始選取的數組索引 超出數組範圍了if (k >= arr.length) {return; }int selectNum = selectedNum(select);// 終止條件2：選中的元素已經等於我們要選擇的數組個數了if (selectNum == COMBINATION_CNT) {for (int j = 0; j < select.length; j++) {if (select[j] == 1) { System.out.print(arr[j]); } } System.out.print("\n"); } else {// 第 k 位被選中select[k] = 1; combination(arr, k+1, select);// 第 k 位未被選中select[k] = 0;// 則從第 k+1 位選擇 COMBINATION_CNT - selectNum 個元素 combination(arr, k+1, select); }}publicstaticvoidmain(String[] args) {int[] arr = {1,2,3,4,5,6,7,8,9};int[] select = {0,0,0,0,0,0,0,0,0};// 一開始從 0 開始選 組合數 combination(arr, 0, select);}
4、求時間/空間複雜度空間複雜度：由於我們用了一個輔助數組 select, 所以空間複雜度是 O(n)時間複雜度：可以看到 f(n) = 2f(n-1)，所以時間複雜度是O(2^n),顯然是指數級別的
畫外音：大家可以考慮一下怎麼優化，提示:每種元素只有選中和被選中的狀態，是不是對應了二進位的 0 和 1，可以考慮用位運算
面試中排列組合的一些變形
經過以上的講解，我相信大家對排列組合的遞歸解法應該是很明白了，不過面試中面試官可能還會對排列組合稍加變形，以進一步考察你的算法水平。
考慮以下情況
在全排列時參與排列的數字都是不相同的， 如果有相同的數字（比如參與排序的是 1， 1，2，3），在使用遞歸進行解題時，需要進行怎樣的改造；在組合中 ，我們的題目是從 n 中選出 m 個數，如果要選出所有組合呢，比如給定 1，2，3，所有的組合是1, 2, 3, 12, 13, 23, 123, 此時以上的遞歸解法又該怎麼改造。聲明：本文為作者投稿，版權歸作者個人所有。