求n個數的子集的三種思路

問題描述：
求0-n-1這n個數的所有子集（這裡認為空集也是一個子集）

算法：
抽象化為對一排n個開關所有可能狀態的尋找

有三種思路：

①遞歸：要求0-n-1這n個開關的狀態子集，只需先求出1-n-1個開關的子集，再對每個子集要麼加上0，要麼加1。

②滿二叉樹：構造一個n+1層的、含有2的n次方個葉節點的滿二叉樹，每個節點的做孩子為0，右孩子為1。例如，對於n=3構造滿二叉樹如下：

root

/ \

0 1

/ \ / \

0 1 0 1

/ \ / \ / \ / \

0 1 0 1 0 1 0 1

然後前序遍歷這課二叉樹。

③二進制：0-pow(2,n)-1這2的n次方個數的二進制表示，就是2的n次方個開關的狀態子集

代碼實現：
①遞歸

#include<iostream>
using namespace std;

int n;
int sum = 0;

void result(int list[], int flag[])
{
cout<<"第"<<++sum<<"個子集"<<endl;//計數
for (int i = 0; i <= n - 1; i++)
if (flag[i] == 1)
cout << list[i] << ' ';
cout << endl;
}

void ziji(int list[], int flag[], int k)
{
if (k <= n - 1)
{
flag[k] = 0;
ziji(list, flag, k + 1);
flag[k] = 1;
ziji(list, flag, k + 1);
}
else
result(list, flag);
}
void main()
{
cin >> n;
int *list = new int[n];
int *flag = new int[n];
for (int i = 0; i<n; i++)
list[i] = i;
ziji(list, flag, 0);

delete[]list;//釋放數組空間
delete[]flag;

system("pause");
}

②滿二叉樹

代碼略

③二進制

#include<iostream>
using namespace std;

int sum = 0;//用於計數

void result(int list[], int flag[],const int n)
{
cout<<"第"<<++sum<<"個子集"<<endl;//計數
for (int i = 0; i <= n - 1; i++)
if (flag[i] == 1)
cout << list[i] << ' ';
cout << endl;
}

void ziji(int list[], int flag[], const int n)
{
int temp = pow(2, n);
for (int i = 0; i < temp; i++)
{
int index = i;
for (int j = 0; j < n; j++)
{
flag[j] = index % 2;
index = index / 2;
}
result(list, flag, n);
}
}
void main()
{
int n;
cin >> n;
int *list = new int[n];
int *flag = new int[n];
for (int i = 0; i<n; i++)
list[i] = i;
ziji(list, flag, n);
delete[]list;
delete[]flag;
system("pause");
}

二叉樹的常見問題及其解決程序 http://www.linuxidc.com/Linux/2013-04/83661.htm

【遞歸】二叉樹的先序建立及遍歷 http://www.linuxidc.com/Linux/2012-12/75608.htm

在JAVA中實現的二叉樹結構 http://www.linuxidc.com/Linux/2008-12/17690.htm

【非遞歸】二叉樹的建立及遍歷 http://www.linuxidc.com/Linux/2012-12/75607.htm

二叉樹遞歸實現與二重指針 http://www.linuxidc.com/Linux/2013-07/87373.htm

二叉樹先序中序非遞歸算法 http://www.linuxidc.com/Linux/2014-06/102935.htm

輕松搞定面試中的二叉樹題目 http://www.linuxidc.com/linux/2014-07/104857.htm