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

浏览数：21 / 时间：2015年06月08日

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;
}