說到回溯法，其實就是暴力搜索，并不是什么高效的算法，最多再剪枝一下。

回溯算法能解決如下問題：

（1）組合問題：N個數(shù)里面按一定規(guī)則找出k個數(shù)的集合

（2）排列問題：N個數(shù)按一定規(guī)則全排列，有幾種排列方式

（3）切割問題：一個字符串按一定規(guī)則有幾種切割方式

（4）子集問題：一個N個數(shù)的集合里有多少符合條件的子集

（5）棋盤問題：N皇后，解數(shù)獨等等回溯法確實不好理解，所以需要把回溯法抽象為一個圖形來理解就容易多了，「在后面的每一道回溯法的題目我都將遍歷過程抽象為樹形結構方便大家的理解」。

本篇主要介紹回溯法的概念和應用。

一、回溯法 – 深度優(yōu)先搜素                       

（1）簡單概述

回溯法思路的簡單描述是：把問題的解空間轉化成了圖或者樹的結構表示，然后使用深度優(yōu)先搜索策略進行遍歷，遍歷的過程中記錄和尋找所有可行解或者最優(yōu)解。

基本思想類同于：

1. 圖的深度優(yōu)先搜索

2. 二叉樹的后序遍歷

分支限界法：廣度優(yōu)先搜索

思想類同于：

1. 圖的廣度優(yōu)先遍歷

2. 二叉樹的層序遍歷

（2）詳細描述

詳細的描述則為：

回溯法按深度優(yōu)先策略搜索問題的解空間樹。首先從根節(jié)點出發(fā)搜索解空間樹，當算法搜索至解空間樹的某一節(jié)點時，先利用剪枝函數(shù)判斷該節(jié)點是否可行（即能得到問題的解）。如果不可行，則跳過對該節(jié)點為根的子樹的搜索，逐層向其祖先節(jié)點回溯；否則，進入該子樹，繼續(xù)按深度優(yōu)先策略搜索。

 回溯法的基本行為是搜索，搜索過程使用剪枝函數(shù)來為了避免無效的搜索。剪枝函數(shù)包括兩類：1. 使用約束函數(shù)，剪去不滿足約束條件的路徑；2.使用限界函數(shù)，剪去不能得到最優(yōu)解的路徑。

問題的關鍵在于如何定義問題的解空間，轉化成樹（即解空間樹）。解空間樹分為兩種：子集樹和排列樹。兩種在算法結構和思路上大體相同。

（3）回溯法應用

當問題是要求滿足某種性質（約束條件）的所有解或最優(yōu)解時，往往使用回溯法。

它有“通用解題法”之美譽。

二、回溯法實現(xiàn) - 遞歸和遞推（迭代）                               

回溯法的實現(xiàn)方法有兩種：遞歸和遞推（也稱迭代）。一般來說，一個問題兩種方法都可以實現(xiàn)，只是在算法效率和設計復雜度上有區(qū)別。

【類比于圖深度遍歷的遞歸實現(xiàn)和非遞歸（遞推）實現(xiàn)】

（1）遞歸：思路簡單，設計容易，但效率低，其設計范式如下：

//針對N叉樹的遞歸回溯方法  
void backtrack (int t)  
{  
    if (t>n) output(x); //葉子節(jié)點，輸出結果，x是可行解  
    else  
       for i = 1 to k//當前節(jié)點的所有子節(jié)點  
        {  
            x[t]=value(i); //每個子節(jié)點的值賦值給x  
            //滿足約束條件和限界條件  
          if (constraint(t)&&bound(t))   
                backtrack(t+1);  //遞歸下一層  
        }  
}

（2）遞推：算法設計相對復雜，但效率高。

//針對N叉樹的迭代回溯方法  
void iterativeBacktrack ()  
{  
    int t=1;  
    while (t>0) {  
        if(ExistSubNode(t)) //當前節(jié)點的存在子節(jié)點  
        {  
            for i = 1 to k  //遍歷當前節(jié)點的所有子節(jié)點  
            {  
                x[t]=value(i);//每個子節(jié)點的值賦值給x  
                if (constraint(t)&&bound(t))//滿足約束條件和限界條件   
                {  
                    //solution表示在節(jié)點t處得到了一個解  
                    if (solution(t)) output(x);//得到問題的一個可行解，輸出  
                    else t++;//沒有得到解，繼續(xù)向下搜索  
                }  
            }  
        }  
        else //不存在子節(jié)點，返回上一層  
        {  
            t--;  
        }  
    }  
}

三、子集樹和排列樹                                                        

（1）子集樹

所給的問題是從n個元素的集合S中找出滿足某種性質的子集時，相應的解空間成為子集樹。

如0-1背包問題，從所給重量、價值不同的物品中挑選幾個物品放入背包，使得在滿足背包不超重的情況下，背包內(nèi)物品價值最大。它的解空間就是一個典型的子集樹。

回溯法搜索子集樹的算法范式如下：

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

（2）排列樹

所給的問題是確定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]);  
      }  
}