回溯法求解n个元素的集合的幂集

过程：

• 树中的根节点表示幂集元素的初始状态（为空集）；
• 叶子节点表示它的终结状态中幂集ρ（A）的8个元素；
• 第i层（i=1,2,3,...,n）层的分支节点，则表示已对集合A中前i-1个元素进行了取/舍处理的当前状态（其中左分支表示“取”，右分支表示“舍”）；
• 将上述问题求解集合的幂集转换为先序遍历这棵状态树的过程。

void Powerset(int i,int n){
	//初始调用：Powerset(1,n)
	if(i>n){
		输出幂集的其中一个元素 
	}else{
		取第i个元素
		Powerset(i+1,n);
		舍第i个元素 
		Powerset(i+1,n);
	}
}  

提示：上述的关键问题是怎么表示“取”和“舍”的过程。

疑问：为什么说求幂集元素的过程是先序遍历状态树的过程呢？

解释：首先要清楚先序遍历的过程是先根后左再右，这样的一个遍历过程；那么在该代码中怎么体现这个先序遍历的过程的呢？从上面画出的集合的幂集二叉树图，可以看到，其实就是通过“取”或者“舍”这个方法来实现的，代码中的auxset[i-1]=set[i-1]就是在进入“左子树”的过程，也就是“取”的过程；而auxset[i-1]=0,则是在进入“右子树”的过程，也就是在“舍”的过程。如果读者还是感觉有点抽象，可以在纸上模拟一下这个过程就能深有体会了。

#define maxn 10
 
//使用数组set表示集合
int set[maxn];
//使用辅助数组auxset表示取和舍的过程
int auxset[maxn];
 
void Powerset(int i,int n){
	if(i>n){
		for(int j=0;j<i-1;j++){
			printf("%d  ",auxset[j]);
		}
		printf("\n");
	}else{
		auxset[i-1]=set[i-1];
		Powerset(i+1,n);
		auxset[i-1]=0;
		Powerset(i+1,n);
	}
}

转载自：https://mydreamambitious.blog.csdn.net/?type=blog