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

問題描述：
給一個集合，集合里面元素都不重復，輸出這個集合的子集。
例如：
輸入：
{1，2，3}
打印：
{1，2，3}
{1，2}
{1，3}
{2，3}
{1}
{2}
{3}
{}//代表空集
思路：
我們用一個等大小的集合，集合中對應的0代表不打印這個元素，集合中對應的1代表打印這個元素。建立兩顆深度為3（集合個數）的滿二叉樹。可以看作哈夫曼編碼，每一個碼代表打印的一個子集。這樣所有的碼都代表一個子集。
比如：
{1，1，1}代表{1，2，3}
{1，1，0}代表{1，2}
{1，0，1}代表{1，3}
…
{0，0，0}代表{}
（注意，1代表打印，0代表不打印）
用代碼解釋會清晰一點，圖下面先寫出代碼，然后再分析代碼，這樣思路會更清晰。

代碼：

void Print_Subset(int* arr, int* brr, int i, int n) {if (i == n){for (int j = 0; j < n; j++){if (brr[j] == 1){printf("%2d", arr[j]);}}printf("\n");}else{brr[i] = 1;Print_Subset(arr, brr, i + 1, n);brr[i] = 0;Print_Subset(arr, brr, i + 1, n);} }int main() {int arr[] = { 1,2,3 };int brr[] = { 0,0,0 };Print_Subset(arr, brr, 0, sizeof(arr)/sizeof(arr[0]));return 0; }

運行結果：

（注意：3下面空兩行，上面一個空行是代表空集，后面一個空行就是換行）
分析代碼：
對于遞歸函數，我們一定要按照層次來分析來想代碼，按照深度來分析，那是系統調用按照深度調用的。

注意遞歸出口是i == n，說明我們的樹已經建立完成了，就可以根據brr的1或者0決定是否要打印arr的元素。

再注意這幾行代碼，我們來分析一下：

else{brr[i] = 1;Print_Subset(arr, brr, i + 1, n);brr[i] = 0;Print_Subset(arr, brr, i + 1, n);}

我們說過了，以深度調用分析，那是系統干的事情，我們只要以層次分析，一層分析完分析下一層，這樣思路才清晰。下面代碼豎著看。
第一層：

第二層（在第一層的基礎上把第一層的函數展開)，要知道每一次brr[i]負值后，后面都會有個函數需要執行：

第三層（在第二層的基礎上把第一層的函數展開)：

再到后面展開函數的時候，已經到了遞歸出口了，即最下面一行的函數遞歸進去都會打印出來一個子集，如下：
根據{1，1，1}打印{1，2，3}
根據{1，1，0}打印{1，2}
根據{1，0，1}打印{1，3}
根據{1，0，0}打印{1}
根據{0，1，1}打印 {2，3}
…

遞歸題，如果一段代碼里出現兩次或者兩次以上遞歸進去函數，那么我們一定要以層次來想函數怎么遞歸，怎么執行，以深度來想函數遞歸出口。

總結

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

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