<script type="text/javascript" src="https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.1/MathJax.js?config=TeX-AMS-MML_HTMLorMML"></script> # Recursion - 遞歸 -------- #### 問題 序列$$ s $$有$$ n $$個成員$$ [x_1,x_2, \dots ,x_n] $$，每個成員可以選取$$ [1,2, \dots ,m] $$這$$ m $$種值。例如當$$ n = 5 $$，$$ m = 3 $$時，序列$$ s $$有如下排列組合： $$ \begin{matrix} [1,1,1,1,1] \\ [1,1,1,1,2] \\ [1,1,1,1,3] \\ [1,1,1,2,1] \\ \cdots \end{matrix} $$ 求$$ s $$的所有排列組合。（與BruteForce問題一樣） #### 解法 BruteForce存在一個問題，外圍for循環的數量是固定的，無法改變。因此我們用遞歸來解決這個問題。假設序列$$ s $$的長度從$$ 0 $$增長到$$ n $$。初始化時令序列為空$$ s = [] $$。 $$ (1) $$ 將序列$$ s $$的長度增加到$$ 1 $$，第$$ 1 $$個元素（唯一的元素）$$ x_1 $$有$$ m $$種選擇，即長度為$$ 1 $$的序列$$ s $$有$$ m $$個排列組合： $$ \begin{matrix} [ 1_1 ] \\ [ 2_1 ] \\ \cdots \\ [ m_1 ] \end{matrix} $$ $$ (2) $$ 將序列$$ s $$的長度增加到$$ 2 $$，得到$$ s = [x_1,x_2] $$，元素$$ x_2 $$的選擇可以看作在第$$ (1) $$輪的每個選擇的基礎上繼續選擇。對于$$ [1_1] $$可以得到$$ m $$個排列組合： $$ \begin{matrix} [ 1_1,1_2 ] \\ [ 1_1,2_1 ] \\ \cdots \\ [ 1_1,m_1 ] \end{matrix} $$ 第$$ (2) $$輪操作后共有$$ m^2 $$個排列組合。重復$$ n $$次這樣的操作，可以得到$$ m^n $$個排列組合。 實際編寫代碼中，在遞歸方程中傳入一個參數$$ 0 \le prev \lt n $$，序列$$ s $$中的成員$$ x_{prev} $$可以取值$$ i \in [1,m] $$，然后$$ prev = prev+1 $$，繼續考慮序列$$ s $$中的下一個成員$$ x_{prev+1} $$。這樣直到當$$ n $$個成員都選擇了一個值時，即產生序列$$ s $$的一種排列組合。通過遞歸可以退回上一個函數棧，從而讓每個成員$$ x_{prev} $$都可以重新選擇。 對于成員數量為$$ n $$，每個成員有$$ m $$種值的序列$$ s $$，遍歷所有排列組合的時間復雜度$$ O(m^n) $$。 -------- #### 源碼 [Recursion.h](https://github.com/linrongbin16/Way-to-Algorithm/blob/master/src/Search/Recursion.h) [Recursion.cpp](https://github.com/linrongbin16/Way-to-Algorithm/blob/master/src/Search/Recursion.cpp) #### 測試 [RecursionTest.cpp](https://github.com/linrongbin16/Way-to-Algorithm/blob/master/src/Search/RecursionTest.cpp)