C++递归求解N个元素的所有子集

引言：我在复习C++遇到了设计递归函数的问题。这个例子，很好的显示了设计递归的方式，思想。这与斐波那数列不同，这个例子更有应用意义。问题：试编写一个递归函数，用来输入n个元素的所有子集。例如：三个元素{a,b,c} 输出： {a,b,c} {ab} {ac} {bc} {a} {b} {c} {}设计思路：

首先，递归是使用的if else结构。

然后，就是if中填条件，再在else写调用自身的函数。
详细思路，请看代码。代码：#include <string.h>
#include <iostream> using namespace std;

void build（char str[],int n）
{
if（n==0）//控制输出
{
cout<<"{";
for（int i=0;i<5;++i）
if（str[i]！=" "）
{
cout<<str[i];
}
cout<<"}"<<endl;
}
else
{
/*** 先递归 ***/
build（str,n-1）;
if（n>0）
{
char newstr[5] = {" "};//去掉就把该位置的元素置成空
/*** 还原之前的状态 ***/ strcpy（newstr,str）; /*** 越来越少的元素 ***/
newstr[n-1]= " ";
/*** 再次递归 ***/
build（newstr,n-1）;
}
}
}测试代码：/***
将整个搜索过程表示为搜索树的形式，问题自然就很简单了。

每一个元素对于一个子集来说，只有两中状态：0表示不属于该子集，1表示属于该子集。
程序中的数组a就是采用这种表示。
因此，搜索过程表示为树的形式就是这样的：

a
0/ 1
b c
0/ 1 0/ 1
...........

因此：
代码中的第一个“trail（t,i+1,n）;”就是搜索当前扩展节点的左子树（因为a[i]此时的值为0）。
代码中的“a[i]=1-a[i];”就是变换当前扩展节点的状态，也就是从左子树换到右子树。
代码中的第二个“trail（t,i+1,n）;”就是搜索当前扩展节点的右子树。

***/
#include <string.h>
#include <iostream>
using namespace std;

void build（char str[],int n）
{
if（n==0）//控制输出
{
cout<<"{";
for（int i=0;i<5;++i）
if（str[i]！=" "）
{
cout<<str[i];
}
cout<<"}"<<endl;
}
else
{
/*** 先递归 ***/
build（str,n-1）;
if（n>0）
{
char newstr[5] = {" "};//去掉就把该位置的元素置成空
/*** 还原之前的状态 ***/
strcpy（newstr,str）;
/*** 越来越少的元素 ***/
newstr[n-1]= " ";
/*** 再次递归 ***/
build（newstr,n-1）;
}
}
}

int main（）
{
char string[5]= "abc ";//实例集合放在数组中
build（string,3）;
return 0;
}其实，设计递归的关键是如何设计。想不到，就百度。看代码也是个快乐的过程，关键是仔细思考。

囫囵吞枣，对于程序员是要不得了。如果你无法做到，用手到后拈来。那么，你学习这个东西是失败的！