1.当所给问题是从n个元素的集合S中找出S满足某种性质的子集时，相应的解空间称为子集树。
例如：n个物品的0-1背包问题所相应的解空间是一棵子集树，这类子集树通常有2^n个叶结点，其结点总数为(2^(n+1))-1。
遍历子集树的算法通常需要(2^n)计算时间。
回溯法搜索子集树的算法一般可以描述如下：
void backtrack(int t) { if (t > n) output(x); else for (int i = 0; i < l; i++) { x[t] = i; if (constraint(t) && bound(t)) backtrack(t + 1); } }
2.当所给问题的确定n个元素满足某种性质的排列时，相应的解空间树称为排列树。
排列树通常有n!个叶结点，因此遍历排列树需要奥秘加(n!)计算时间。
例如：全排列、货郎担问题...
回溯法搜索排列树的算法一般可以描述如下：
void backtrack(int t) { if (t > n) output(x); else for (int i = t; i < n; i++) { swap(x[t], x[i]); if (constraint(t) && bound(t)) backtrack(t + 1); swap(x[t], x[i]); } }
