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

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

如何通過程序求解？
方法一：
暴力法，為什么是暴力法？因為暴力是機(jī)器唯一聽得懂的語言。
如何暴力？
對一個空的字符串添加字母，添加三次，這個字母是ABC這三個中的一個。
每添加完三個字母后，也就是得到一個排列以后，我們要檢查這是不是個有效的排列。
如果是就輸出，否則跳過。
有效的排列是指什么？是排列的所有數(shù)字都不相同，這里我使用雙重循環(huán)來判斷。
這個判斷函數(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;
    }

}

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

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

第一個問題，實際上是代碼編寫技巧的問題，比較容易解決，使用模板即可。那我們先來解決第一個問題！
Let"s start！

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

現(xiàn)在我們逆向思維來考慮(主動和被動)！
之前考慮的是寫for循環(huán)來填充候選答案向量，現(xiàn)在換個想法，我們的候選答案向量要被填充。
當(dāng)候選答案向量的每一維都被填充好，那么就產(chǎn)生了一個候選答案。
怎樣用代碼來描述這樣一個過程呢？遞歸！雖然很難想到，但是使用遞歸確實可以描述這個過程。
在遞歸的過程中，使用一個變量k表示當(dāng)前正在填充的候選答案向量的下標(biāo)(0到n-1，n是排列長度)。那么
當(dāng)k等于n的時候，也就代表當(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代表前面的變量是后面{}里的某個元素。
這是一個基于3維解空間的深度優(yōu)先搜索！

至此，第一個問題已經(jīng)解決！
接下來我們來看第二個問題！
Exciting！

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

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++) {
            //每次填充完就判斷，如果不合法，則根本不會向下進(jìn)行!
            temp[k] = num[i];
            if(is_Legal(temp,k+1))
            dfs(num, k + 1, n, temp);
        }
    }

    //cur代表這是第幾次填充，第cur次填充對應(yīng)著填充
    //第cur-1下標(biāo)的地方，因此上面調(diào)用時為下標(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;
    }

}

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

不知道讀者是否聽說過剪枝這個詞但卻一直無法理解它的含義。
可以明確是，上面的這個判斷就是所謂的剪枝！
為什么理解不了剪枝？因為從代碼和算法里只能看到剪，而看不到枝。既然是剪枝，那么必須要又枝給你剪才行啊！！！那么這枝在哪呢？

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

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

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

當(dāng)然也可以不使用一個額外的表去存儲哪些字母已經(jīng)在答案向量中，而是直接在答案向量中查找，因為答案向量已經(jīng)記錄了哪些字母在，哪些字母不在了，只不過這樣的話查詢的時間消耗比用Hash表大！不過原理一樣，讀者可以自行嘗試！

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

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);
                //下一個for循環(huán)的時候就是放該層的
                // 下一個可以放的字母，這輪循環(huán)放的是這個字母
                //那么下一輪循環(huán)顯然放的不是這個字母了，那么這個字母需要被
                //移除出hash表
                hash[i] = false;
            }
    }

}

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

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

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

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

為什么要從暴力法開始講起？因為暴力是機(jī)器唯一聽得懂的語言。