回溯法与树的遍历求集合的幂子集

回溯法是设计递归的一种常用方法，它的求解过程实质上就是一个先序遍历一棵"状态树"的过程,只是这棵树不是遍历前预先建立的而是隐含在遍历过程中的。

拿求解集合幂子集举例：

集合A={ {1,2,3}, {1,2}, {1,3}, {1}, {2,3},{2},{3},{}};      //{}表示空集合

从集合A的每一个元素的角度看，它只有两种状态：或者是属于幂集的元素集，或不属于幂集元素集，则求幂集的过程就可以看成是依次对集合A中的元素进行"取"，"舍"的过程,并且可以用下图中的二叉树，来表示过程中幂集的变化状态。

 

树的根节点表示，幂集元素的初始状态，为空集，叶子节点表示他的终极状态，可以看到，叶子节点就是将来要求的幂集。而且当集合的元素个数为n，则状态二叉树的叶子位于第n层(根节点是第0层)，并且数目是：2^n，

下面是代码：

 

void OutPut(char *dest)
{
    for(; *dest; dest++)    cout<<*dest<<" ";
    cout<<endl;
}

void GetPowerSet(int i, char A[], char B[])
{
    if( i==strlen(A) )    OutPut(B);
    else
    {
        char x=A[i];    //GetElem
        int k=strlen(B);

        B[k]=x;        GetPowerSet(i+1, A, B);        //左子树
        B[k]='0';    GetPowerSet(i+1, A, B);        //右子树
    }
}

int main()
{
    char A[]={"123"};
    int size_B=strlen(A)+1;
    char* B=new char[size_B];
    memset(B, 0, size_B);
    GetPowerSet(0, A, B);
    delete B;
    return 0;
}

运行以后可以看到，输出顺序就是前序遍历二叉树，叶子的输出顺序。