回溯法：从问题的某一种状态（初始状态）出发，搜索从这种状态出发所能达到的所有“状态”，当一条路走到“尽头”的时候（不能再前进），再后退一步或若干步，从另一种可能“状态”出发，继续搜索，直到所有的“路径”（状态）都试探过。这种不断“前进”、不断“回溯”寻找解的方法，就称作“回溯法”。

回溯算法：

1. 形式化解的结构，根据形式描述，建立解树。解树的每个非叶子节点描述一类可行解，而叶子节点通常描述一个可行解。
2. 利用深度优先搜索解空间。算法根据目标函数，确定节点所代表解的优化程度，当访问叶子节点时，解就唯一的确定了；访问中间节点时还没法唯一的确定，无法计算目标函数值。利用启发函数和分支定界，避免移动到不可能产生解的子空间。问题的解空间通常是在搜索问题的解的过程中动态产生的，这是回溯算法的一个重要特性。

解空间：

回溯算法的解空间一般分为：子集树和排列树。

子集树：二叉树来表示，较为熟悉。

排列树：第一层树有n个选择，第二层有n-1个选择，以此类推，直到叶子节点。

子集树和排列树都是“隐式图”。

子集树遍历的伪代码：

void backtrack(int  t)

{
     if(t>n)   
        output(x);
     else
        for(int i=0; i<=1; i++)
      {  
             x[t] = i; 
             backtrack(t+1);
       }  
}

排列树遍历的伪代码：

     void backtrack(int  t)

    {
       if(t>n)  

           output(x);
       else      

          for(int i=t; i<=n; i++)
          {
            swap(x[t], x[i]);
            backtrace(t+1);
            swap(x[t], x[i]);       

         }     

   }