摘要：它真的是深度優(yōu)先搜索嗎是真的嗎是真的如果是的話，那它的搜索空間解空間是什么是向量組成的集合，而。既然深度優(yōu)先搜索剪枝回溯。

什么是全排列？
從n個(gè)不同元素中任取m（m≤n）個(gè)元素，按照一定的順序排列起來(lái)，叫做從n個(gè)不同元素中取出m個(gè)元素的一個(gè)排列。當(dāng)m=n時(shí)所有的排列情況叫全排列。
那么ABC的全排列有哪些？根據(jù)定義得到：
ABC
ACB
BAC
BCA
CAB
CBA

如何通過(guò)程序求解？
方法一：
暴力法，為什么是暴力法？因?yàn)楸┝κ菣C(jī)器唯一聽(tīng)得懂的語(yǔ)言。
如何暴力？
對(duì)一個(gè)空的字符串添加字母，添加三次，這個(gè)字母是ABC這三個(gè)中的一個(gè)。
每添加完三個(gè)字母后，也就是得到一個(gè)排列以后，我們要檢查這是不是個(gè)有效的排列。
如果是就輸出，否則跳過(guò)。
有效的排列是指什么？是排列的所有數(shù)字都不相同，這里我使用雙重循環(huán)來(lái)判斷。
這個(gè)判斷函數(shù)復(fù)雜度較高為O(N2)，但是容易理解，所以目前就先不使用更高效的算法。

java 代碼：

public class Main {

    public static void main(String[] args) throws Exception{
        //等待求解的全排列集合
        char[]num = new char[]{"A","B","C"};

        for(int i = 0;i < num.length;i++)
            for (int j = 0;j < num.length;j++)
                for (int k = 0;k < num.length;k++)
                {
                    char[]temp = new char[3];
                    temp[0] = num[i];
                    temp[1] = num[j];
                    temp[2] = num[k];
                    if(is_Legal(temp))
                        System.out.println(temp);
                }

    }

    static boolean is_Legal(char[]temp)
    {
        for(int i = 0;i < temp.length;i++)
            for(int j = i+1;j < temp.length;j++)
                if(temp[i] == temp[j])
                    return false;
        return true;
    }

}

可以看到，通過(guò)3個(gè)for循環(huán)，不斷填充候選答案的第0項(xiàng)，第1項(xiàng)，第2項(xiàng)。這樣可以產(chǎn)生所有的候選答案，然后通過(guò)對(duì)每個(gè)候選答案判斷是否合法來(lái)選擇輸出與否。

不過(guò)這里產(chǎn)生了兩個(gè)問(wèn)題。
1：如果現(xiàn)在求的全排列不是3個(gè)數(shù)，而是10個(gè)數(shù)甚至20個(gè)數(shù)，那怎么辦？要寫(xiě)十多個(gè)for循環(huán)？這樣豈不是要累死。
2：是否有必要產(chǎn)生所有的候選答案？換句話說(shuō)，有些候選答案在產(chǎn)生過(guò)程中就已經(jīng)是不合法的了，那么我們還有必要將這個(gè)候選答案完全“填充”嗎(為什么要加深"填充"？因?yàn)楹苤匾?？
比如說(shuō)AAB這個(gè)候選答案，在產(chǎn)生AA的時(shí)候就已經(jīng)不合法了（不管第三個(gè)數(shù)填什么都是非法的）。

第一個(gè)問(wèn)題，實(shí)際上是代碼編寫(xiě)技巧的問(wèn)題，比較容易解決，使用模板即可。那我們先來(lái)解決第一個(gè)問(wèn)題！
Let"s start！

我們發(fā)現(xiàn)，每個(gè)for循環(huán)做的事情，就是填充候選答案向量的某個(gè)位置，并且是固定的，第一個(gè)for就填充候選答案向量的第1個(gè)位置(下標(biāo)是0)，第二個(gè)for循環(huán)填充第2個(gè)位置，第三個(gè)for循環(huán)填充第3個(gè)位置。
那么如果寫(xiě)100個(gè)for循環(huán)，原理也是一樣，不過(guò)就是填充第100(候選答案向量的下標(biāo)是99)個(gè)位置而已。

現(xiàn)在我們逆向思維來(lái)考慮(主動(dòng)和被動(dòng))！
之前考慮的是寫(xiě)for循環(huán)來(lái)填充候選答案向量，現(xiàn)在換個(gè)想法，我們的候選答案向量要被填充。
當(dāng)候選答案向量的每一維都被填充好，那么就產(chǎn)生了一個(gè)候選答案。
怎樣用代碼來(lái)描述這樣一個(gè)過(guò)程呢？遞歸！雖然很難想到，但是使用遞歸確實(shí)可以描述這個(gè)過(guò)程。
在遞歸的過(guò)程中，使用一個(gè)變量k表示當(dāng)前正在填充的候選答案向量的下標(biāo)(0到n-1，n是排列長(zhǎng)度)。那么
當(dāng)k等于n的時(shí)候，也就代表當(dāng)前正在填充的是候選答案向量的下標(biāo)是n，而n已經(jīng)超出了該向量，那么也就意味著填充結(jié)束！

java 代碼：

public class Main {

    public static void main(String[] args) throws Exception{
        //等待求解的全排列集合
        char[]num = new char[]{"A","B","C"};

       dfs(num,0,num.length,new char[num.length]);
    }

    static void dfs(char[]num,int k,int n,char[]temp)
    {
        if(k == n)
        {
            if(is_Legal(temp))
                System.out.println(temp);
            return;
        }
        for(int i = 0;i < num.length;i++) {
            temp[k] = num[i];
            dfs(num, k + 1, n, temp);
        }
    }

    static boolean is_Legal(char[]temp)
    {
        for(int i = 0;i < temp.length;i++)
            for(int j = i+1;j < temp.length;j++)
                if(temp[i] == temp[j])
                    return false;
        return true;
    }
}

細(xì)心的讀者可能注意到了，遞歸函數(shù)的名字是dfs。這是什么意思呢？這是深度優(yōu)先搜索！
搜索？遍歷？傻傻分不清。

它真的是深度優(yōu)先搜索嗎？是真的嗎？
是真的！
如果是的話，那它的搜索空間(解空間)是什么？
是向量[x,y,z]組成的集合，而x,y,z in {"A","B","C"}。in代表前面的變量是后面{}里的某個(gè)元素。
這是一個(gè)基于3維解空間的深度優(yōu)先搜索！

至此，第一個(gè)問(wèn)題已經(jīng)解決！
接下來(lái)我們來(lái)看第二個(gè)問(wèn)題！
Exciting！

是否有必要產(chǎn)生所有候選答案？當(dāng)然沒(méi)有！只要我們?cè)诋a(chǎn)生候選答案向量的時(shí)候，每一次填充完都判斷
這次填充是否合法，如果不合法則不再繼續(xù)填充。(不過(guò)第一次填充不需要判斷，想想為什么？)

java 代碼：

public class Main {

    public static void main(String[] args) throws Exception{
        //等待求解的全排列集合
        char[]num = new char[]{"A","B","C"};

       dfs(num,0,num.length,new char[num.length]);
    }

    static void dfs(char[]num,int k,int n,char[]temp)
    {
        if(k == n)
        {
            System.out.println(temp);
            return;
        }
        for(int i = 0;i < num.length;i++) {
            //每次填充完就判斷，如果不合法，則根本不會(huì)向下進(jìn)行!
            temp[k] = num[i];
            if(is_Legal(temp,k+1))
            dfs(num, k + 1, n, temp);
        }
    }

    //cur代表這是第幾次填充，第cur次填充對(duì)應(yīng)著填充
    //第cur-1下標(biāo)的地方，因此上面調(diào)用時(shí)為下標(biāo)+1,也就是k+1
    static boolean is_Legal(char[]temp,int cur)
    {
        for(int i = 0;i < cur;i++)
            for(int j = i+1;j < cur;j++)
                if(temp[i] == temp[j])
                    return false;
        return true;
    }

}

也可以在最前面那種三個(gè)for循環(huán)里每一次都判斷，比較簡(jiǎn)單，讀者可以自行嘗試。

不知道讀者是否聽(tīng)說(shuō)過(guò)剪枝這個(gè)詞但卻一直無(wú)法理解它的含義。
可以明確是，上面的這個(gè)判斷就是所謂的剪枝！
為什么理解不了剪枝？因?yàn)閺拇a和算法里只能看到剪，而看不到枝。既然是剪枝，那么必須要又枝給你剪才行?。。。∧敲催@枝在哪呢？

看一下我畫(huà)的圖，最左邊是候選答案下標(biāo)。然后右邊表明了每一層填充的是哪些字母。這個(gè)填充過(guò)程像是一顆三叉樹(shù)，但是這個(gè)樹(shù)實(shí)際上不存在的，這只是邏輯上的樹(shù)而已，而這個(gè)邏輯上的樹(shù)(或圖)上的路徑我們把它稱之為枝，剪枝的意思就是把這棵邏輯上的樹(shù)(或圖)的某條路徑剪去。
那么對(duì)于這個(gè)問(wèn)題，當(dāng)填充完第1層的時(shí)候，哪些路徑被剪去了呢？答案是AA，BB,CC。
不過(guò)這個(gè)圖我畫(huà)的并不完整，因?yàn)槿鄙倭说?層(只有0，1，2層)，第三層是最終的答案，讀者可以自行嘗試畫(huà)出。

至此第二個(gè)問(wèn)題也已經(jīng)解決！
讀者的內(nèi)心是不是“這和回溯有毛線關(guān)系??？”別著急，接著看。
Interesting！
不知道讀者有沒(méi)有覺(jué)得，上面的寫(xiě)法很丑陋？我們剪枝與否為什么填充完結(jié)果才能判斷？
難道就不能一開(kāi)始就知道哪個(gè)字母能填哪個(gè)不能填嗎？
就像是站在上帝的視角上看這個(gè)問(wèn)題，好像通靈萬(wàn)物，未卜先知，洞悉一切一樣。
這個(gè)能確實(shí)做到，不過(guò)不能未卜先知，但是可以利用之前的結(jié)果來(lái)先知！

我們?cè)谶f歸程序中添加一個(gè)boolean類型的數(shù)組(或hash表)，來(lái)記錄哪個(gè)字母現(xiàn)在已經(jīng)在候選答案向量中了，這樣一來(lái)，凡是不在的我都可以添加進(jìn)去，而已經(jīng)在候選答案向量中的不可添加。

當(dāng)然也可以不使用一個(gè)額外的表去存儲(chǔ)哪些字母已經(jīng)在答案向量中，而是直接在答案向量中查找，因?yàn)榇鸢赶蛄恳呀?jīng)記錄了哪些字母在，哪些字母不在了，只不過(guò)這樣的話查詢的時(shí)間消耗比用Hash表大！不過(guò)原理一樣，讀者可以自行嘗試！

需要注意的是，添加一個(gè)字母到候選答案向量中的時(shí)候，就要把該字母加入表中，而當(dāng)這個(gè)字母不在答案向量中時(shí)需要及時(shí)移除。

java 代碼：

public class Main {

    public static void main(String[] args) throws Exception{
        //等待求解的全排列集合
        char[]num = new char[]{"A","B","C"};

       backtrack(num,0,num.length,new char[num.length],new boolean[num.length]);
    }

    static void backtrack(char[]num,int k,int n,char[]temp,boolean[]hash)
    {
        if(k == n)
        {
            System.out.println(temp);
            return;
        }
        for (int i = 0;i < num.length;i++)
            //如果不在候選答案向量中則添加該字母
            if( !hash[i] )
            {
                hash[i] = true;
                temp[k] = num[i];
                backtrack(num,k+1,n,temp,hash);
                //下一個(gè)for循環(huán)的時(shí)候就是放該層的
                // 下一個(gè)可以放的字母，這輪循環(huán)放的是這個(gè)字母
                //那么下一輪循環(huán)顯然放的不是這個(gè)字母了，那么這個(gè)字母需要被
                //移除出hash表
                hash[i] = false;
            }
    }

}

函數(shù)名是backtrack，意義是回溯！
從各個(gè)角度看，這里的回溯和剛才的方法唯一不同的就是名字好聽(tīng)，比較高大上，代碼簡(jiǎn)短優(yōu)美。
有人可能會(huì)說(shuō)上面的那種做法是后剪枝，回溯是先剪枝。不過(guò)其實(shí)兩者是一回事，先剪晚剪都是
剪。
因此?。?！
回溯其實(shí)就是剪了枝的深度優(yōu)先搜索！??！

說(shuō)到底，回溯就是個(gè)深度優(yōu)先搜索算法，即便是剪了枝的，也掩蓋不了它是個(gè)暴力解法。

既然：深度優(yōu)先搜索+剪枝=回溯。
那么：寬度優(yōu)先搜索+剪枝=？？？
這個(gè)我之后有時(shí)間再寫(xiě)。

搜索很暴力，很無(wú)腦，很低效，可是有一種稱之為記憶化的方法，卻能夠明顯改善它的性能。
甚至可以使得搜索的效率比強(qiáng)大的動(dòng)態(tài)規(guī)劃都要好！
這就像是小孩子一樣，沒(méi)受教育之前很頑劣，受過(guò)教育之后就好像變了一個(gè)人一樣。
有關(guān)記憶化搜索，我也有時(shí)間再寫(xiě)！

為什么要從暴力法開(kāi)始講起？因?yàn)楸┝κ菣C(jī)器唯一聽(tīng)得懂的語(yǔ)言。