閱讀之前

請確認您能夠理解函數(shù)及其遞歸調用。

快速入門

深度優(yōu)先搜索（DFS羹应，即Depth First Search）屬于圖算法的一種，也被氫切的稱為回溯算法劫灶，本質還是打暴力。其過程簡要來說是對每一個可能的分支路徑深入到不能再深入為止涌穆，而且每個節(jié)點只能訪問一次。在非圖論的應用中祝沸，DFS常用于設計回溯遞歸算法罩锐，本次我們主要圍繞DFS的基本應用即回溯搜索為中心展開講解。

考慮全排列問題蟀拷，即按照字典序輸出自然數(shù) 到 所有不重復的排列的個數(shù)與排列的方式问芬，即 的全排列，要求所產生的任一數(shù)字序列中不允許出現(xiàn)重復的數(shù)字挡鞍。要求編寫程序遍歷所有可能的情況并輸出墨微。我們先來看一個簡單的情況，此時用腦子很容易想到一共有6種排列谴分，分別是。

我們是如何想到這6個數(shù)字的呢蓖康？首先倒信，我們以1作為第1位，之后選擇2作為第2位，剩下一個3作為第3位卡辰，得到123；之后我們回到第一位為1的情況允蚣，再選擇剛才沒選的3作為第2位，最后選擇剩下的2作為第3位，得到132同衣。這樣1作為第1位的情況就全部遍歷完成浪秘，我們回到最開始辕翰，再選擇2作為第1位沟沙，之后選擇1作為第2位赎瞎，以此往復，直到把6種情況全部遍歷完畢。

我們以此為以據(jù)設計算法哟绊，首先考慮基本的連續(xù)選擇過程，由于對于全排列而言痰憎，每個數(shù)字只能使用一次票髓，我們使用一個數(shù)組vis來存儲每一個數(shù)組是否已被使用，當選擇下一個數(shù)字時铣耘，我們檢查這個數(shù)字是否已經被使用洽沟，如果沒被使用，則選擇這個數(shù)字并更新狀態(tài)蜗细，如過已經被使用吊骤，那么嘗試選擇下一個數(shù)字眷细。

最重要的在于“回溯”過程地熄，我們在上面提到過，當?shù)谝淮芜x擇完成闽晦，選擇完成一次回溯巧还，重新跳回到第2位的選擇星瘾。由于第3位選擇的3已經被釋放边翁，我們應該將vis數(shù)組中的3位置修改為false。由于2已經被選擇部凑，接著繼續(xù)嘗試向下選擇3浩聋，此時3未被訪問過梧兼，接下來將3作為第2為欲虚，生成132驯鳖。

第一次回溯

#include <iostream>

using namespace std;
void dfs(int layer);

int n,ans;
int vis[14] = {};

int main()
{
    cin >> n;
    dfs(1);
    cout << ans << endl;

    return 0;
}

void dfs(int layer)
{
    if (layer > n)
        ans++;

    for (int i = 1; i <= n; ++i)
    {
        if (!vis[i])
        {
            vis[i] = true;
            dfs(layer + 1);
            vis[i] = false;
        }
    }
}

我們來簡單的解讀一下這份遞歸代碼中的核心部分——dfs函數(shù)幌甘。

1. 生成答案潮售。當layer > n時，代表產生了一種新答案锅风，此時累加答案酥诽。

if (layer > n)
    ans++;

2. 遍歷搜索樹的一層。對于每深入的一位皱埠，我們都從起點開始遍歷肮帐，覆蓋每一種情況。

for (int i = 1; i <= n; ++i)

3. 產生情況边器。對每次要取的數(shù)字训枢，判斷它是否被訪問過。如果是忘巧，則不進入內部的處理恒界，循環(huán)繼續(xù)尋找下一位。如果它沒有被訪問過砚嘴，進入更深的一層遞歸十酣，同時將該數(shù)設為已訪問。

if (!vis[i])
{
    vis[i] = true;
    dfs(layer + 1);
}

4. 回溯际长。當遍歷至終點耸采，更深層的dfs函數(shù)退出。需要注意的是工育，相對于上一層dfs函數(shù)而言虾宇，更深層的dfs函數(shù)占用了vis[i]，此時要從淺層的dfs翅娶，通過下一個數(shù)字來訪問深層的dfs文留，也就是回溯過程好唯，將已經被占用的數(shù)字重新置否竭沫，將被占用的vis[i]設為未占用燥翅。

vis[i] = false;

至此完成整個深度優(yōu)先搜索過程。

接下來我們考慮如何輸出答案的排列蜕提。我們可以使用一個新數(shù)組arrange來記錄該數(shù)字每一位的情況森书，在每一次成功占用數(shù)字時，我們將arrange[layer]（也就是第layer層占用的數(shù)字）設置為i谎势，表示第layer層使用了數(shù)字i凛膏。當每次完成遞歸也就是layer > n時，我們輸出這個數(shù)組的全部元素即可脏榆，為了美觀我們位每個元素保留5個場寬猖毫。

#include <iostream>
#include <iomanip>

using namespace std;
void dfs(int layer);

int n;
int arrange[14] = {}, vis[14] = {};

int main()
{
    cin >> n;
    dfs(1);
    return 0;
}

void dfs(int layer)
{
    if (layer > n)
    {
        for (int i = 1; i <= n; ++i)
            cout << setw(5) << arrange[i];
        cout << endl;
    }

    for (int i = 1; i <= n; ++i)
    {
        if (!vis[i])
        {
            vis[i] = true;
            arrange[layer] = i;
            dfs(layer + 1);
            vis[i] = false;
        }
    }
}

再次梳理執(zhí)行思路如下：

• 對于每一層layer：
  • 如果layer > n，打印當前排列arrange[1...n]
  • 否則须喂，對每個數(shù)字i（1到n）：
    • 如果vis[i]為假：
      • 設置vis[i]為真
      • 將i放入arrange[layer]
      • 遞歸調用dfs(layer + 1)
      • 遞歸返回后，設置vis[i]回假

這里無需重置arrange[layer]坞生，結論是顯然的仔役，這個數(shù)組中的元素會在每次數(shù)字占用時被覆蓋。

排列問題

深度優(yōu)先搜索在排列問題中非常常見是己。上文我們正是通過一個基本的全排列問題引入了DFS又兵。下面我們考慮“三連擊”問題：將 共 個數(shù)分成三組，分別組成三個三位數(shù)卒废，且使這三個三位數(shù)的比例是 沛厨，試求出所有滿足條件的三個三位數(shù)，若無解摔认，輸出 No!!!逆皮。輸入，级野；輸出若干行页屠，每行 個數(shù)字。按照每行第一個數(shù)字升序排列蓖柔。

初看這題可能毫無頭緒辰企，上文提到過，DFS本質就是打暴力况鸣，想想這個題能不能暴力求解牢贸？這個題的暴力思路是明顯的，我們枚舉1-9這9個數(shù)字的全排列镐捧，然后把它們分成三組潜索，那么這個題就可以被轉換為全排列問題臭增。事實上，我們可以把每次遞歸竹习，都可以不加限制的對搜索樹的一層進行枚舉的情況都稱作全排列誊抛。

現(xiàn)在轉回到這個問題上來，很容易構建它的搜索樹：

搜索樹

按照模板構建深度優(yōu)先搜索整陌，

首先拗窃，準備數(shù)組vis記錄所有訪問過的元素，數(shù)組arrange記錄每一位的情況泌辫。

1. 生成答案随夸。當layer > 9時，代表產生了一種新答案震放，此時我們按照arrange的每三位進行分割宾毒，形成三個數(shù)字。之后殿遂，由于題目要求這三個三位數(shù)的比例是 诈铛，我們通過一個語句num1 * C == num3 * A && num1 * B == num2 * A來驗證，如果符合要求勉躺，則輸出癌瘾。

if (layer > 9)
{
    auto num1 = arrange[1] * 100 + arrange[2] * 10 + arrange[3];
    auto num2 = arrange[4] * 100 + arrange[5] * 10 + arrange[6];
    auto num3 = arrange[7] * 100 + arrange[8] * 10 + arrange[9];

    if (num1 * C == num3 * A && num1 * B == num2 * A)
    {
        flag = true;
        cout << num1 << " " << num2 << " " << num3 << endl;
    }
}

2. 遍歷搜索樹的一層。該樹任意一層有9種情況饵溅，代表數(shù)字妨退。

for (int i = 1; i < 10; ++i)

3. 產生情況。我們遍歷每一個數(shù)字蜕企，如該數(shù)字未被使用咬荷，我們記錄該數(shù)字并更新狀態(tài)為已使用，并加以此狀態(tài)進入下一層遞歸轻掩。

if (!vis[i])
{
    vis[i] = true;
    arrange[layer] = i;
    dfs(layer + 1);
}

4. 回溯幸乒。將已經被占用的數(shù)字重新置否，將被占用的vis[i]設為未占用唇牧。

vis[i] = false;

5. 特判罕扎。此題需要注意的是，若無解丐重，輸出 No!!!腔召。我們定義一個標志flag。在第1步中扮惦，一旦產生合法的答案臀蛛，flag就會被更新為true。到最后時，我們看一下flag的狀態(tài)浊仆，如果仍為false客峭，說明沒有任何解，需要輸出 No!!!抡柿。

if (!flag)
    cout << "No!!!" << endl;
return 0;

本題完整代碼如下：

#include <iostream>
using namespace std;

int A, B, C;
int vis[10] = {0},arrange[10] = {-1};
bool flag = false;
void dfs(int layer);

int main()
{
    cin >> A >> B >> C;
    dfs(1);

    if (!flag)
        cout << "No!!!" << endl;
    return 0;
}

void dfs(int layer)
{
    if (layer > 9)
    {
        auto num1 = arrange[1] * 100 + arrange[2] * 10 + arrange[3];
        auto num2 = arrange[4] * 100 + arrange[5] * 10 + arrange[6];
        auto num3 = arrange[7] * 100 + arrange[8] * 10 + arrange[9];

        if (num1 * C == num3 * A && num1 * B == num2 * A)
        {
            flag = true;
            cout << num1 << " " << num2 << " " << num3 << endl;
        }
    }

    for (int i = 1; i < 10; ++i)
    {
        if (!vis[i])
        {
            vis[i] = true;
            arrange[layer] = i;
            dfs(layer + 1);
            vis[i] = false;
        }
    }
}

子集問題

我們來看一道有趣的配料問題：Perket 是一種流行的美食舔琅。為了做好 Perket，廚師必須謹慎選擇食材沙绝，以在保持傳統(tǒng)風味的同時盡可能獲得最全面的味道搏明。你有 種可支配的配料鼠锈。對于每一種配料闪檬，我們知道它們各自的酸度 和苦度 。當我們添加配料時购笆，總的酸度為每一種配料的酸度總乘積粗悯；總的苦度為每一種配料的苦度的總和。眾所周知同欠，美食應該做到口感適中样傍，所以我們希望選取配料，以使得酸度和苦度的絕對差最小铺遂。另外衫哥，我們必須添加至少一種配料，因為沒有任何食物以水為配料的襟锐。輸入第一行一個整數(shù) 撤逢，表示可供選用的食材種類數(shù)。接下來 行粮坞，每行 個整數(shù) 和 蚊荣，表示第 種食材的酸度和苦度。輸出一行一個整數(shù)莫杈，表示可能的總酸度和總苦度的最小絕對差互例。

這個問題說到底還是這些酸度和苦度的全排列。但這問題相比起上一個有兩個明顯的不同點筝闹，首先媳叨，酸度和苦度并不能任意排，我們可以使用一個結構體配對存儲关顷，然后對其全排：

struct ingredient
{
    int s;
    int b;
}arr[11];

另一個最大的不同就是這題的“全排列”不是說一定要到最后一層的所有情況糊秆，也就是說，給了我們種材料解寝，我們不是一定要加種扩然，而是可以加1種，可以加2種...可以加種聋伦，當然也可以加種夫偶，這種情況相當于求了集合的所有子集界睁。我們要找出最優(yōu)解，可以畫圖看一下兵拢。

搜索樹

1. 生成答案。每次進入深搜時腻扇，我們都要嘗試此時的答案债热，即可能的總酸度和總苦度的最小絕對差。并且比較D與目前最小答案ans的大小幼苛，如果窒篱，那么更新ans為D。需要特別注意的是舶沿，剛進入時墙杯，vis數(shù)組全為false，此時未進入求值括荡，而我們給答案賦值時高镐，酸度的初值為1，苦度的初值為0畸冲。 嫉髓，也就是說求出來的這個最小差為1，我們需要記錄一下是否進入了計算的過程召夹，如果沒有進入岩喷，那么就不進行賦值。否則進行正常賦值监憎。

if (layer > n) return;

int sour = 1, bitter = 0;
bool changed = false;
for (int i = 0; i < n; ++i)
{
    if (vis[i])
    {
        sour *= arr[i].s;
        bitter += arr[i].b;
        changed = true;
    }
}

if (changed)
    ans = min(ans, abs(sour - bitter));

2. 遍歷搜索樹的一層纱意。任意一層有種情況。代表選擇鲸阔。

for (int i = 0; i < n; ++i)

3. 產生情況偷霉。我們遍歷arr中的每一種配料，并使用vis進行記錄映射褐筛，如該調料未被使用类少，記錄該數(shù)字并更新狀態(tài)為已使用并加以此狀態(tài)進入下一層遞歸。

if (!vis[i])
{
    vis[i] = true;
    dfs(layer + 1);
}

4. 回溯渔扎。將已經被占用的數(shù)字重新置否硫狞，將被占用的vis[i]設為未占用。

vis[i] = false;

合并以上思路，便可以使用以下簡單的代碼解決該問題：

#include<iostream>

using namespace std;

struct ingredient
{
    int s;
    int b;
}arr[11];
bool vis[11];
int n,ans = 2147483647;

void dfs(int layer);

int main()
{
    cin >> n;

    for (int i = 0; i < n; ++i)
        cin >> arr[i].s >> arr[i].b;

    dfs(0);
    cout << ans << endl;
    return 0;
}

void dfs(int layer)
{
    if (layer > n) return;

    int sour = 1, bitter = 0;
    bool changed = false;
    for (int i = 0; i < n; ++i)
    {
        if (vis[i])
        {
            sour *= arr[i].s;
            bitter += arr[i].b;
            changed = true;
        }
    }

    if (changed)
        ans = min(ans, abs(sour - bitter));

    for (int i = 0; i < n; ++i)
    {
        if (!vis[i]) 
        {
            vis[i] = true;
            dfs(layer + 1);
            vis[i] = false;
        }
    }
}

組合問題

組合與排列最大的區(qū)別就是組合不包含重復的排列残吩。舉個例子财忽，對于數(shù)字中抽取三個數(shù)字，而言泣侮，全排列可以包含等等活尊，對于組合而言隶校，這三種排列都是數(shù)字的組合深胳，算作同一種組合。那么如何尋找組合呢宁仔？事實上稠屠，組合和排列的區(qū)別在于，組合需要對重復的排列去重翎苫。

首先我們觀察一個簡單的情況：不加詳細考慮的先認為以1為首位的所有組合已經枚舉完成，下面以2作為首位枚舉榨了，顯然是一個重復的組合（已被枚舉）那么移動第2位的開始位置至第2個元素2煎谍，由于元素2已經在首位被使用，這種情況被忽略龙屉，接下來第2位移動到3呐粘，如果第3位從第1個元素開始，會得到转捕，與重復作岖，那么移動第3位的開始位置至第2個元素2，由于2已經被使用五芝，接下來第2位移動到3痘儡，又由于3已經被使用，接下來第2位移動到4枢步，產生新的組合沉删，之后繼續(xù)以上過程得到新的組合。

回溯過程（應該說是兩輪回溯而不是兩次）

解決組合問題：排列與組合是常用的數(shù)學方法，其中組合就是從 個元素中抽出 個元素（不分順序且 ）采幌，我們可以簡單地將 個元素理解為自然數(shù) 恍涂，從中任取 個數(shù)。現(xiàn)要求你輸出所有組合植榕。例如 再沧，所有組合為：。輸入一行兩個自然數(shù) 尊残。輸出所有的組合炒瘸，每一個組合占一行且其中的元素按由小到大的順序排列，每個元素占三個字符的位置寝衫，所有的組合也按字典順序顷扩。

我們盡可能地通過修改板子地方式實現(xiàn)，我們修改第2步慰毅，遍歷搜索樹的一層隘截。對于每深入的一位，我們都從比上一位大的地方開始遍歷汹胃，覆蓋每一種情況婶芭。

for (int i = start; i <= n; ++i)

之后修改第3步，產生情況着饥。對每次要取的數(shù)字犀农，判斷它是否被訪問過。如果是宰掉，則不進入內部的處理呵哨，循環(huán)繼續(xù)尋找下一位。如果它沒有被訪問過轨奄，進入更深的一層遞歸孟害，同時將該數(shù)設為已訪問。同時向dfs函數(shù)中傳入當前遍歷到的位置挪拟，并+1作為下一層的起始值挨务。

if (!vis[i])
{
    vis[i] = true;
    dfs(layer + 1,i + 1);
}

最后修改函數(shù)簽名，增加一個參數(shù)start接收這個位置即可舞丛。

void dfs(int layer,int start);

完整代碼如下所示：

#include<iostream>
#include <iomanip>

using namespace std;

int n, r;
int vis[22], combine[22];
void dfs(int layer, int start);

int main()
{
    cin >> n >> r;
    dfs(1,1);

    return 0;
}

void dfs(int layer,int start)
{
    if (layer > r)
    {
        for (int i = 1; i < r + 1; ++i)
            cout << setw(3) << combine[i];
        cout << endl;
        return;
    }

    for (int i = start; i < n + 1; ++i)
    {
        if (!vis[i])
        {
            vis[i] = true;
            combine[layer] = i;
            dfs(layer + 1, i + 1);
            vis[i] = false;
        }
    }
}

坐標問題

深度優(yōu)先搜索在二維數(shù)組（坐標系）中應用廣泛耘子。一方面，可以解決回溯搜索問題球切；另一方面谷誓，衍生出的Flood Filling一類算法可以解決連通性問題。

“過河卒”是一個經典的算法問題：棋盤上 點有一個過河卒吨凑，需要走到目標 點捍歪。卒行走的規(guī)則：可以向下户辱、或者向右。同時在棋盤上 點有一個對方的馬糙臼，該馬所在的點和所有跳躍一步可達的點稱為對方馬的控制點庐镐。因此稱之為“馬攔過河卒”。棋盤用坐標表示变逃， 點 必逆、 點 ，同樣馬的位置坐標是需要給出的揽乱。

題目示例

現(xiàn)在要求你計算出卒從 點能夠到達 點的路徑的條數(shù)名眉，假設馬的位置是固定不動的，并不是卒走一步馬走一步凰棉。輸入一行四個正整數(shù)损拢，分別表示 點坐標和馬的坐標。輸出一個整數(shù)撒犀，表示所有的路徑條數(shù)福压。

現(xiàn)在問題從一維上升到了二維，我們依然還是先構建搜索樹或舞，搜索樹有了荆姆，思路也就有了。但這時我們構建搜索樹時可能遇到難以逾越的天塹：我們無從獲知每一次選擇的情況是什么嚷那。這時候我們可以重新思考搜索樹的實質胞枕。每一層的選擇實質上是相對于上一層，下一層可以如何選擇魏宽。在本題中，對于上一層的坐標决乎，下一次可以向下移動队询，此時坐標變?yōu)?img class="math-inline" src="https://math.jianshu.com/math?formula=a_%7Bx%2B1%2Cy%7D" alt="a_{x+1,y}" mathimg="1">，也可以向右移動构诚，此時坐標變?yōu)?img class="math-inline" src="https://math.jianshu.com/math?formula=a_%7Bx%2Cy%2B1%7D" alt="a_{x,y+1}" mathimg="1">蚌斩。也就是說我們的搜索樹每層有2種情況。

那么這棵樹有多少層呢范嘱？我們無從獲知送膳。但是這棵樹的層數(shù)真的有這么重要嗎？回想樹層數(shù)的作用丑蛤，不過是用于確定終止條件而已叠聋，而這個題的終止條件并不是選擇多少個格子，而是到達終點受裹，所以這棵樹的層數(shù)根本就不重要碌补。

搜索樹

完成了思考虏束，接下來，我們古法炮制dfs代碼厦章。

1. 生成答案镇匀。當此時搜索的坐標達到終點的坐標時，將答案累計1袜啃。我們存儲馬及其控制點的坐標至數(shù)組forbid中汗侵，如果傳入的坐標在forbid中，函數(shù)立即返回群发；并且晰韵，如果坐標超出了坐標系的界限，函數(shù)也立即返回也物。

if (x < 0 || y < 0 || x > dest[0] || y > dest[1])
    return;

for (int i = 0; i < 8; ++i)
    if (forbid[x][y])
        return;

if (x == dest[0] && y == dest[1])
{
    ans++;
    return;
}

2. 遍歷搜索樹的一層宫屠。任意一層有種情況。也就是兩個dfs函數(shù)的調用滑蚯。
3. 產生情況浪蹂。如果當前位置未訪問垮耳，就訪問接下來的兩個臨近位置圆凰，并且完成對vis數(shù)組的更新如上邑遏，不再贅述缓醋。

if (!vis[x][y])
{
    vis[x][y] = true;
    dfs(x + 1, y);
    dfs(x, y + 1);
}

4. 回溯呻顽。將已經被掃過的數(shù)字接觸占用旭蠕，將被占用的vis[i]設為未占用吗购。

vis[x][y] = false;

整理上述思路喊递，容易構建深搜如下：

#include<iostream>
#include <iomanip>

using namespace std;

int dest[2],ans = 0;
bool vis[21][21] = {0},forbid[21][21] = {0};
void dfs(int x, int y);

int main()
{
    int hx, hy;
    cin >> dest[0] >> dest[1];
    cin >> hx >> hy;

    int dx[] = { -2,-1,1,2,2,1,-1,-2 };
    int dy[] = { 1,2,2,1,-1,-2,-2,-1 };

    forbid[hx][hy] = true;
    for (int i = 0; i < 8; ++i)
    {
        if (hx + dx[i] <= dest[0] && hy + dy[i] <= dest[1])
            forbid[hx + dx[i]][hy + dy[i]] = true;
    }

    dfs(0, 0);
    cout << ans << endl;
    return 0;
}

void dfs(int x,int y)
{
    if (x < 0 || y < 0 || x > dest[0] || y > dest[1])
        return;

    for (int i = 0; i < 8; ++i)
        if (forbid[x][y])
            return;

    if (x == dest[0] && y == dest[1])
    {
        ans++;
        return;
    }

    if (!vis[x][y])
    {
        vis[x][y] = true;
        dfs(x + 1, y);
        dfs(x, y + 1);
        vis[x][y] = false;
    }
}疤剑，

鞏固提高

坐標系中的問題不一定非得要深搜每一個格子滑绒，例如“八皇后”問題：
一個如下的 的跳棋棋盤，有六個棋子被放置在棋盤上隘膘，使得每行疑故、每列有且只有一個，每條對角線（包括兩條主對角線的所有平行線）上至多有一個棋子弯菊。

棋盤圖片

不難發(fā)現(xiàn)书妻，每一行/每一列都是只能放置一個棋子的船响。我們可以以行構建搜索樹。每一行中躲履，我們都有（在示例中為6）種放置方法见间，很容易構建搜索樹。

搜索樹

之后進行深搜即可工猜。這里的深搜終止條件是同一列或者對角線已經被其它棋子占用米诉。我們可以用三個數(shù)組col[n]、diagp[n]和diagn[n]存儲同一列篷帅、斜率為正和負的對角線的占用情況史侣。列可以用直接用坐標表示，如何表示一條對角線呢魏身？觀察可以發(fā)現(xiàn)惊橱，兩條對角線的其中一條為定值，另外一條為定值箭昵。根據(jù)這些推斷直接套上dfs板子即可税朴，不再贅述：

#include<iostream>

using namespace std;
void dfs(int layer);
int col[30], diagp[30], diagn[30], status[15],ans = 0, n = 0;

int main()
{
    cin >> n;
    dfs(1);

    cout << ans << endl;
    return 0;
}

void setval(int l, int i, int val)
{
    status[l] = i;
    col[i] = val;
    diagp[l + i] = val;
    diagn[l - i + n] = val;
}

void dfs(int layer)
{
    if (layer > n)
    {
        ans++;
        if (ans <= 3)
        {
            for (int i = 1; i <= n; ++i)
                cout << status[i] << " ";
            cout << endl;
        }
    }

    for (int i = 1; i <= n; ++i)
    {
        if (col[i] || diagp[layer + i] || diagn[layer - i + n]) continue;
        setval(layer, i, 1);
        dfs(layer + 1);
        setval(layer, i, 0);
    }
}