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

下面举一个例子：求含n个元素的集的幂集：

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

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

解题思路：求幂集的过程可看成是依次对集合A中的元素进行取或舍的过程。

1.选择合适的数据结构——假设以线性表表示集合。

2.树根结点表示幂集元素的初始状态（空集），叶子结点表示终结状态（幂集的元素），第i层表示已对前i-1个元素进行了取舍的当前状态

下面是代码：

1 #include 
     
       2 #include 
      
        3  4 using namespace std; 5  6 // 输出集合元素 7 void printSet(list
       
         p) 8 { 9     size_t num = p.size();10     if(!num)11         cout<<"空集\n";12     else13     {14         list
        
         ::iterator pos = p.begin();15         for( ;pos!= p.end() ; pos++)16         {17             cout<<(*pos)<<"\t";18         }19         cout<<"\n"<
         
          n 说明已经完成的最后元素的选择，输出 27 void GetPowerSet(int i,list
          
            a,list
           
             &b)28 {29 int n = a.size();30 if(i >= n)31 printSet(b);32 else33 {34 list
            
             ::iterator it = a.begin();35 int j = 0;36 while(j++ < i)37 it++;38 int tmp = *it;39 b.push_back(tmp);40 GetPowerSet(i+1,a,b);41 b.pop_back();42 GetPowerSet(i+1,a,b);43 }44 } 45 46 int main(int argc,char* argv[])47 {48 list
             
               la,lb;49 la.push_back(10);50 la.push_back(3);51 52 GetPowerSet(0,la,lb); 53 return 0;54 }