求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