求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本文永久更新链接地址：http://www.linuxidc.com/Linux/2014-12/110864.htm