有许多问题,可以利用试探和回溯的搜索技术求解。
求解的过程实际是先序遍历一棵“状态树”的过程。
例1:有集合A = {1, 2, ...n},求A的全部子集。
思路:从求全部子集(幂集)这个事情上,实际上对每个元素只有两个状态:要么在一个子集中,要么不在。
因此,可以逐一对A中每个元素进行“取”和“舍”,从而构造一棵完全二叉树。
算法如下:
注意这里是1~n,不是0~n
void mj(int n, int pos, int* flag)
{
i[......]
有许多问题,可以利用试探和回溯的搜索技术求解。
求解的过程实际是先序遍历一棵“状态树”的过程。
例1:有集合A = {1, 2, ...n},求A的全部子集。
思路:从求全部子集(幂集)这个事情上,实际上对每个元素只有两个状态:要么在一个子集中,要么不在。
因此,可以逐一对A中每个元素进行“取”和“舍”,从而构造一棵完全二叉树。
算法如下:
注意这里是1~n,不是0~n
void mj(int n, int pos, int* flag)
{
i[......]