Tag Archives: 树的幂集

数据结构重读 – 回溯法与树的遍历 (幂集问题 八皇后问题)

有许多问题,可以利用试探和回溯的搜索技术求解。

求解的过程实际是先序遍历一棵“状态树”的过程

例1:有集合A = {1, 2, ...n},求A的全部子集。

思路:从求全部子集(幂集)这个事情上,实际上对每个元素只有两个状态:要么在一个子集中,要么不在。

因此,可以逐一对A中每个元素进行“取”和“舍”,从而构造一棵完全二叉树。

算法如下:

注意这里是1~n,不是0~n
void mj(int n, int pos, int* flag)
{
    i[......]

继续阅读