回溯法

回溯法是这样一个遍历过程，首先从根节点出发，深度优先，不断往下遍历子结点，当子节点遍历完之后，回溯到父节点，看看还有没有其他没遍历的子节点，若有，继续往下遍历，遍历完子节点后，再回溯到父结点，依次不断，知道所有结点都遍历完为止。

比如要求集合{0，1，2}的所有子集，过程如下：

1．找到0，然后看还有没有子节点，发现有子节点01

2．沿着01往下，再看有没有子节点，发现有子节点012

3．再看012有没有子节点，发现没有，则回溯到父节点01，看其还有没有其他子节点

4． 01没有其他子节点，则继续回溯到父节点0，看0有没有其他子节点，发现有子节点02

5．沿着02往下，然后看有没有其他子节点，

6． 02没有子节点，则回溯到父节点0，看0有没有其他子节点

7． 0没有其他子节点了，继续回溯到父节点“根”，看“根”有没有其他子节点，发现有子节点1

8．沿着1往下，看1有没有其他子节点，发现有子节点12

9．沿着12往下，看有没有其他子节点

遍历的子集的先后顺序如下：

012

2
回溯法