题目：
    试编写一个递归函数，用来输出n 个元素的所有子集。例如，三个元素{a, b, c} 的所有子集是：{ }（空集），{a}, {b}, {c}, {a, b}, {a, c}, {b, c} 和{a, b, c}。



这道题很难……

[[it] 本帖最后由 linren 于 2008-7-8 16:34 编辑 [/it]]

这道题很易

恩……
是吗……
我再好好想一想好了……

#include <iostream>
using namespace std;

int list[100]={0};

template<class T>
void Print(const T E[],int x)
{
    cout<<"{";
    for(int i=0;i<x-1;i++)
    {
        cout<<E[list[i]]<<", ";
    }
    cout<<E[list[x-1]]<<"} ";
}

template<class T>
void F(const T E[],int n,int x=0,int y=0)
{
    if(x==0)
    {
        cout<<"{}";
        return;
    }
    if(x==n)
    {
        cout<<"{";
        for(int j=0;j<n-1;j++)
        {
            cout<<E[j]<<", ";
        }
        cout<<E[n-1]<<"}";
        return;
    }

    if(x>y)
    {
        if(y==0)
        {
            for(int k=0;k<n-x+1;k++)
            {
                list[y]=k;
                if(y==x-1)
                {
                    Print(E,x);
                }
                else
                {
                    y++;
                    F(E,n,x,y);
                    y--;
                }
            }
            return;
        }

        for(int i=list[y-1]+1;i<n;i++)
        {
            list[y]=i;
            if(y==x-1)
            {
                Print(E,x);
            }
            else
            {
                y++;
                F(E,n,x,y);
                y--;
            }
        }
        list[y]=0;
    }
}

template<class T>
void eXF(const T E[],int n)
{
    for(int i=0;i<=n;i++)
    {
        F(E,n,i);
        cout<<endl;
    }
}

int main()
{
    char a[5]={'a','b','c','d','e'};
    eXF(a,5);
    return 0;
}

这道题很难是对的。我看过这种题目的类型。看到这种题，心中要建立一个虚拟树。利用树来解决会好一些

用那么复杂么？

dfs一下就可以了
实质生成个序列集

[bo]回复：[/bo]


这两种方法好像都不错的样子，可以写出来吗……
我的数据结构的知识全部还给老师了，最近正在重新学习中……


[bo]新内容：[/bo]
上次写的算法效率不是很好，所以修改了一下……

#include <iostream>
using namespace std;

int* list;

template<class T>
void Print(const T* E,int x)
{
    cout<<"{";
    for(int i=0;i<x-1;i++)
    {
        cout<<E[list[i]]<<", ";
    }
    cout<<E[list[x-1]]<<"} ";
}

template<class T>
void F(const T* E,int n,int x=0,int y=0)
{
    if(x==0)
    {
        cout<<"{}";
        return;
    }
    if(x==n)
    {
        cout<<"{";
        for(int j=0;j<n-1;j++)
        {
            cout<<E[j]<<", ";
        }
        cout<<E[n-1]<<"}";
        return;
    }

    if(x>y)
    {
        if(y==0)
        {
            for(int k=0;k<n-x+1;k++)
            {
                list[y]=k;
                if(y==x-1)
                {
                    Print(E,x);
                }
                else
                {
                    y++;
                    F(E,n,x,y);
                    y--;
                }
            }
            return;
        }

        for(int i=list[y-1]+1;i<n-x+y+1;i++)
        {
            list[y]=i;
            if(y==x-1)
            {
                Print(E,x);
            }
            else
            {
                y++;
                F(E,n,x,y);
                y--;
            }
        }
        list[y]=0;
    }
}

template<class T>
void eXF(const T* E,int n)
{
    list=new int[n];
    for(int i=0;i<=n;i++)
    {
        F(E,n,i);
        cout<<endl;
    }
    delete [] list;
    list=0;
}

int main()
{
    char a[7]={'a','b','c','d','e','f','g'};
    try
    {
        eXF(a,7);
    }
    catch(const char *s)
    {
        cout<<s<<endl;
        return 1;
    }

    cout<<endl<<endl;    
    int b[5]={1,2,3,4,5};
    try
    {
        eXF(b,5);
    }
    catch(const char *s)
    {
        cout<<s<<endl;
        return 1;
    }
    return 0;
}


/**********************************************************
运行结果：
{}
{a} {b} {c} {d} {e} {f} {g}
{a, b} {a, c} {a, d} {a, e} {a, f} {a, g} {b, c} {b, d} {b, e} {b, f} {b, g} {c,
 d} {c, e} {c, f} {c, g} {d, e} {d, f} {d, g} {e, f} {e, g} {f, g}
{a, b, c} {a, b, d} {a, b, e} {a, b, f} {a, b, g} {a, c, d} {a, c, e} {a, c, f}
{a, c, g} {a, d, e} {a, d, f} {a, d, g} {a, e, f} {a, e, g} {a, f, g} {b, c, d}
{b, c, e} {b, c, f} {b, c, g} {b, d, e} {b, d, f} {b, d, g} {b, e, f} {b, e, g}
{b, f, g} {c, d, e} {c, d, f} {c, d, g} {c, e, f} {c, e, g} {c, f, g} {d, e, f}
{d, e, g} {d, f, g} {e, f, g}
{a, b, c, d} {a, b, c, e} {a, b, c, f} {a, b, c, g} {a, b, d, e} {a, b, d, f} {a
, b, d, g} {a, b, e, f} {a, b, e, g} {a, b, f, g} {a, c, d, e} {a, c, d, f} {a,
c, d, g} {a, c, e, f} {a, c, e, g} {a, c, f, g} {a, d, e, f} {a, d, e, g} {a, d,
 f, g} {a, e, f, g} {b, c, d, e} {b, c, d, f} {b, c, d, g} {b, c, e, f} {b, c, e
, g} {b, c, f, g} {b, d, e, f} {b, d, e, g} {b, d, f, g} {b, e, f, g} {c, d, e,
f} {c, d, e, g} {c, d, f, g} {c, e, f, g} {d, e, f, g}
{a, b, c, d, e} {a, b, c, d, f} {a, b, c, d, g} {a, b, c, e, f} {a, b, c, e, g}
{a, b, c, f, g} {a, b, d, e, f} {a, b, d, e, g} {a, b, d, f, g} {a, b, e, f, g}
{a, c, d, e, f} {a, c, d, e, g} {a, c, d, f, g} {a, c, e, f, g} {a, d, e, f, g}
{b, c, d, e, f} {b, c, d, e, g} {b, c, d, f, g} {b, c, e, f, g} {b, d, e, f, g}
{c, d, e, f, g}
{a, b, c, d, e, f} {a, b, c, d, e, g} {a, b, c, d, f, g} {a, b, c, e, f, g} {a,
b, d, e, f, g} {a, c, d, e, f, g} {b, c, d, e, f, g}
{a, b, c, d, e, f, g}


{}
{1} {2} {3} {4} {5}
{1, 2} {1, 3} {1, 4} {1, 5} {2, 3} {2, 4} {2, 5} {3, 4} {3, 5} {4, 5}
{1, 2, 3} {1, 2, 4} {1, 2, 5} {1, 3, 4} {1, 3, 5} {1, 4, 5} {2, 3, 4} {2, 3, 5}
{2, 4, 5} {3, 4, 5}
{1, 2, 3, 4} {1, 2, 3, 5} {1, 2, 4, 5} {1, 3, 4, 5} {2, 3, 4, 5}
{1, 2, 3, 4, 5}
Press any key to continue
**********************************************************/

利用树是一种经典的方法，写一个函数，要20行代码就行了，还一种方法是非递归的。好像是利用队列。算法，由于本人接触这样问题少，也很少写代码，有一练习书上看到的

原来是这样……
我想……
非递归实现起来一定会更难的……

这个题目是程序员考试书上的。。。我以前写过了