有一类求一组解，或者求全部解，或者求最优解的问题，可以利用 “试探”和“回溯”的搜索技术来求解。
例如：求含n个元素的集合的幂集合（全集）
解法一：“分治法”进行“递归算法设计”，
递归规定义：基本项（终结状态） + 归纳项（如何从当前状态转化到终结状态，也就是原问题和子问题之间的转化）
递归设计的实质：当一个复杂的问题可以分解为若干子问题来处理时，其中某些子问题和原问题有相同的特征属性，则可以利用和源问题相同的分析处理方法。（例如汉诺塔的问题中，可以分解为3个子问题，（1）将编号为1至n-1的n-1个圆盘从X塔座移到Y塔座；（2）将编号为n的圆盘从X塔座移到Z塔座（3）将编号为1至n-1的圆盘从Y塔座移到Z塔座。
关于“树”的问题，我们很容易会想到用“递归”，如果其他结构的数据类型也可以用“树”的角度去思考的话那可能会很容易找到问题的解答思路。
例如求A={1,2,3}的幂集 即p(A)={{1,2,3},{1,2},{1,3},{2,3},{1},{2},{3},Φ};
如果我们用树的角度去思考这个问题，那我们得到的会是（这里默认最底层节点为空集Φ）
这属于分治法进行递归设计，我们每次都需要将原问题分为
而从另一个角度来看这个问题，幂集中的每个元素是一个集合，它可以是空集，也可以是包含A中一个元素的集合，也可以是两个，三个，最后等于集合A本身。所以从集合A的每个元素来看，它只有两个状态：它或者属于幂集的元素集，或者不属于幂集的元素集，所以求A的幂集就可以看成是依次对A中的元素进行“取”或者“舍”。
我们同样用树型结构来表达这一思路，并最终在树形结构上完成幂集的求解，假设初始化时树只有一个根节点，节点内容为空，表示Φ（这个集合时所有集合的幂集所包含的）。然后我们对集合A中的元素依次进行取舍操作，“取“操作表示将元素连接到原节点的左分支，”舍“操作则保留原节点内容并作为其右分支，最后我们可以生成下面这样的树：
所以求幂集的过程也就是对这颗状态树进行先序遍历
Void PowSet(int I, int n)
{
If( i> n) {输出一个集合，其元素为集合A中的元素，即输出A的幂集的一个元素}
Else
{
取得A集合中的第i个元素，也就是向树的左边走
PowerSet(i+1,n); //对树的左枝做同样操作
舍弃A集合中的第i个元素，也就是向树的右边走
PowerSet(i+1,n); //对树的右枝做同样操作
}
}
//具体实现
Void GetPowerSet(int i, List A, List B)
{
//用线性表A表示集合A,线性表B表示A的幂集的元素集合。
If( i > ListLength(A) ) Output(B);
Else
{
GetElem(A,i,x); //将A集合中的第i个元素赋值给x
K = ListLength(B); //得到当前B的长度
ListInsert(B,k+1,x); // 进行取操作
GetPowerSet(i+1,A,B);
ListDelete(B,k+1,x); //进行舍操作
GetPowerSet(i+1,A,B);
}
}
{reference：数据结构-严蔚敏
author：aga j
}