遞歸函數：以層次來想函數遞歸，以深度來想遞歸出口。

問題：
給出一個集合，輸入這個集合所有的排列集合。
例如：
輸入：
{1，2，3}
輸出：
{1，2，3}
{1，3，2}
{2，1，3}
{2，3，1}
{3，1，2}
{3，2，1}
思路：
全排列，就是不斷交換兩個元素，打印。
將所有可以交換的兩個元素都交換一遍，都打印一遍，加上本來的排列，打印出來的就是我們的全排列。
所以我們焦點就放在了交換上面，怎么交換兩個元素會使邏輯清晰。我們自己手寫全排列的時候，一般都是先以第一個元素為首的全排列寫完，再以第二個元素為首的全排列寫完…直至寫完。
我們先確定1這個位置不動，對剩下的數進行全排列，剩下的數的全排列第一個數加上1，那么以1為首的全排列就結束了。那么怎么對剩下的全排列進行排序呢？剩下的元素中，第一個元素不動，對剩下的元素進行全排列…一直遞歸，那么遞歸出口就是我們遞歸到最后一個元素，不需要對最后一個元素進行全排列。
看著代碼分析會清晰一點：

void Perm(int* arr, int k, int m) {if (k == m - 1){for (int i = 0; i < m; i++){printf("%2d", arr[k]);}}else{for (int i = k; i < m; i++){swap(arr[i], arr[k]);Perm(arr, k + 1, m);swap(arr[i], arr[k]);}} }

我們以層次來分析這個代碼，首先將第一個元素和第一個元素本身進行交換，再將第一個元素本身和第二個元素交換，第一個元素和第三個元素交換…直至第一個元素和最后一個元素進行完交換。
第一層：產生【1，2，3】 【2，1，3】 【3，2，1】三個數組。下一層遞歸，會對數組的除去第一個元素的剩下元素進行交換。剩下元素的第一個元素和第一個元素交換，剩下元素的第一個元素和第二個元素交換，剩下元素的第一個元素和第三個元素交換…

遞歸函數我們按層次分析，出來的就會是一個樹，在這里我們相當于在葉子節點時，打印數組的值。

總結

以上是生活随笔為你收集整理的递归与分治——全排列问题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。