如：A={1，2，3}，則A的冪集P（A）={{1，2，3}，{1，2}，{1，3}，{1}，{2，3}，{2}，{3}，{ }}。

求一個集合的冪集就是求一個集合的所有的子集，方法有窮舉法，分治法，回溯等，這里主要介紹一下回溯法。

回溯法是設(shè)計遞歸過程的一種重要的方法，它的求解過實質(zhì)上是一個先序遍歷一棵“狀態(tài)樹”的過程，只是這棵樹不是遍歷前預(yù)先建立的，而是隱含在遍歷過程中的。

冪集中的每個元素是一個集合，它或是空集，或含集合A中一個元素，或含集合A中兩個元素…… 或等于集合A。反之，從集合A 的每個元素來看，它只有兩種狀態(tài)：它或?qū)賰缂臒o素集，或不屬冪集的元素集。則求冪集p(A)的元素的過程可看成是依次對集合A中元素進(jìn)行“取”或“舍”的過程，并且可以用一棵二叉樹來表示過程中冪集元素的狀態(tài)變化過程，樹中的根結(jié)點表示冪集元素的初始狀態(tài)（空集）；葉子結(jié)點表示它的終結(jié)狀態(tài)，而第i層的分支結(jié)點，則表示已對集合A中前i-1個元素進(jìn)行了取舍處理的當(dāng)前狀態(tài)（左分支表示取，右分支表示舍 ）。因此求冪集元素的過程即為先序遍歷這棵狀態(tài)樹的過程。

具體算法如下：

C/C++描述：

 1#include <iostream>
 2#include <cstring>
 3#include <ctype.h>
 4#include <stdlib.h>
 5#include <string>
 6using namespace std;
 7 
 8char a[100];
 9char b[100];
10 
11void GetPowerSet(int i, char a[])
12{
13    char x;
14    int k;
15    int len = strlen(a);
16    if(i >= len)
17    {
18        if(b[0])
19            cout << b <<  endl;
20        else
21            cout << "XX" << endl;  // 表示空集
22    }
23    else
24    {
25        x = a[i];
26        k = strlen(b);
27        b[k] = x;
28        GetPowerSet(i+1, a);
29        b[k] = 0;
30        GetPowerSet(i+1, a);
31    }
32}
33 
34 
35int main()
36{
37    while(scanf("%s", a) != EOF)
38    {
39        printf("%s的冪集是:\n", a);
40        printf("------------\n");
41        GetPowerSet(0, a);
42        printf("------------\n");
43    }
44}