上一遍文章我們過了一次廣度優(yōu)先算法，算是比較好理解的，因為模式比較固定，使用隊列再進行while() 循環(huán)，既可以滿足大部分時候的需求。這一次我們來開始學(xué)習(xí)/復(fù)習(xí)一下我們的深度優(yōu)先算法。深度優(yōu)先算法其實在很多地方都可以應(yīng)用到，其實在我的看法，只要搜索集合相對固定，并且使用到遞歸的算法都可以算是深度優(yōu)先。而且在學(xué)習(xí)完回溯算法的很多題目之后，大家也可以更直觀的體驗到，很多時候回溯也是暴力搜索的一種程序上的實現(xiàn)而已。所以，
1.回溯
2.深度優(yōu)先
3.暴力搜索
這三種算法，名字雖然不同，但是都在某些情況下是有很大的共同成分的。大家在看完題目之后可以好好感受一下。
那么進入正題
1.理解遞歸
如果是計算機專業(yè)的同學(xué)可能可以忽略這一小節(jié)。
[圖片上傳失敗...(image-1a1a5f-1518421713974)]
其實遞歸的方法和一般的方法有什么區(qū)別呢？答案是完全沒有，遞歸的方法和一般的方法完全沒有區(qū)別。一個標準的方法/函數(shù)，都是需要在方法/函數(shù)棧里面進行調(diào)用和返回的。舉個栗子。
static void a(){
b();
}
static void b(){
c();
}
static void c(){
System.out.println("methods")
}
public static void main(String[] args){
a();
}
下面這段代碼在方法棧中的執(zhí)行過程如下兩圖所示。
如上圖所示，所有的方法在執(zhí)行結(jié)束之后都會返回,return,這個return，代表的是return到該方法的調(diào)用者，也就是執(zhí)行該方法的方法內(nèi)，也就是上一層中。
理解了這個，遞歸也就很好理解，同樣是使用方法/函數(shù)棧，只不過是調(diào)用的方法是相同的方法而已。
2.理解回溯
理解回溯，我們先從一個例題來看一下。
我們有一個集合/列表，含有若干整數(shù)(不含有重復(fù))，例如:{1，2，3}。 求該集合的全排列。
{1,2,3}
{1,3,2}
{2,1,3}
{2,3,1}
{3,1,2}
{3,2,1}
從直觀的感覺來說，第一眼遇到這個題目，我們可以這么去抽象的構(gòu)思:
我們按照步驟/狀態(tài)來抽象的話，我們每一刻都有一個可用集合，一個答案集合。每一步都需要從可用集合里面抽取一個元素加入到答案集合。在答案集合滿了（或者是可用集合空了）的時候，代表我們獲取了一個答案，這時需要
向后，往可用集合內(nèi)部退回元素。再重新做抽取的步驟，往答案集合中放置元素。
可以看出來，我們每次獲取答案都要向上退后一步，回到之前的狀態(tài)，選取不同的元素放入結(jié)果集合。這個過程其實就是我們之前所講的回溯。至于怎么樣遍歷集合，根據(jù)題目的要求我們可以有不同的策略，一般的回溯算法都是涉及列表的遍歷，for循環(huán)足矣。
我們來看看代碼
public List<List> getPermutation(List<Integer> list){
List result = new ArrayList<>();
permutateHelper(result,new ArrayList<>(), list, new HashSet<Integer>());
return result;
}
private void permutateHelper(List result, List<Integer> temp,List<Integer> list, HashSet<Integer> visited){
//如果temp，temp答案集合滿了，我們加入到最終的結(jié)果集合內(nèi)。
if(temp.size() == list.size()){
result.add(new ArrayList(temp));
}
else{
//直接使用for循環(huán)進行對原集合的遍歷
for(int i = 0; i< list.size();i++){
//如果沒有visit過，進行遞歸
if(!visited.contains(list.get(i))){
int current = list.get(i);
temp.add(current);
visited.add(current);
//進入下一層遞歸
permutateHelper(result,temp,list,visited);
visited.remove(current);
//這里需要直接remove掉最后一個元素，因為我們的全部的下一層遞歸已經(jīng)結(jié)束，所以可以把該層的數(shù)字刪掉，進入for循環(huán)的下一個遍歷的開始了。這里這個remove的動作就是我們所謂的“回溯”
temp.remove(temp.size()-1);
}
}
}
}
從以上代碼我們可以看出，回溯算法其實就是普通的遞歸，但是加上了對集合遍歷(for 循環(huán))的過程，大家可以體會一下一個小小的區(qū)別。假如在以上的代碼中，我們的temp不刪除最后一個元素，改成這樣：
private void permutateHelper(List result, List<Integer> temp,List<Integer> list, HashSet<Integer> visited){
if(temp.size() == list.size()){
result.add(new ArrayList(temp));
}
else{
for(int i = 0; i< list.size();i++){
if(!visited.contains(list.get(i))){
int current = list.get(i);
temp.add(current);
visited.add(current);
//進入下一層遞歸,不刪除最后一個元素，每次都創(chuàng)建一個新的temp列表
permutateHelper(result,new ArrayList<>(temp),list,visited);
visited.remove(current);
}
}
}
}
簡單的一行的修改，最后的答案也是對的(先不說這個修改浪費了多少空間)，可是卻完全的改變了我們要的回溯的本質(zhì)，沒有向前退的這個動作，這個程序就變成了單純的遞歸，暴力搜索了。
關(guān)于排列組合的題目，還有更加難的，比如集合中有重復(fù)元素怎么辦，如果不只是求全排列，而是求子集呢？
有興趣的同學(xué)可以看看leetcode上的題目:
1.Permutation II
2.Subset
相信大家對所謂的回溯已經(jīng)有點理解了。我們再來一個難一點點的題目。
3. 電話鍵盤
例題來自leetcode的一道關(guān)于電話鍵盤的題目
這個題目就是說，在手機上按幾個數(shù)字鍵，對應(yīng)可能產(chǎn)生的所有可能的字母的集合。比如在手機上按23，就是從{a,b,c}和{d,e,f}中各取一個放入答案集合中。
這題和上一題的區(qū)別是，搜索集合不再是一個固定的大集合了，而是若干的小集合，每個數(shù)字對應(yīng)一個小集合，滿足搜索結(jié)果的答案的標準也不一樣，不再是以集合的元素數(shù)量為標準，而是以我們的輸入數(shù)字的數(shù)量為標準。
我們直接看代碼
public List<String> letterCombinations(String digits) {
if (digits == null || digits.length() == 0) {
return new ArrayList<>();
}
///先初始化手機按鍵的數(shù)字和字母的關(guān)系
String[] one = { "" };
String[] two = { "a", "b", "c" };
String[] three = { "d", "e", "f" };
String[] four = { "g", "h", "i" };
String[] five = { "j", "k", "l" };
String[] six = { "m", "n", "o" };
String[] seven = { "p", "q", "r", "s" };
String[] eight = { "t", "u", "v" };
String[] nine = { "w", "x", "y", "z" };
String[] zero = { "" };
HashMap<Integer, String[]> map = new HashMap<>();
map.put(0, zero);
map.put(1, one);
map.put(2, two);
map.put(3, three);
map.put(4, four);
map.put(5, five);
map.put(6, six);
map.put(7, seven);
map.put(8, eight);
map.put(9, nine);
ArrayList<String> result = new ArrayList<>();
int[] allNum = new int[digits.length()];
for (int i = 0; i < digits.length(); i++) {
allNum[i] = Integer.parseInt(digits.substring(i, i + 1));
}
phoneNumberHelper(result, new StringBuilder(), 0, allNum, map);
return result;
}
private void phoneNumberHelper(ArrayList<String> result, StringBuilder current, int index, int[] allNum,
HashMap<Integer, String[]> com) {
//如果找到一個排列，加入答案中
if (index == allNum.length) {
result.add(current.toString());
return;
} else {
//使用for循環(huán)，遍歷當前該數(shù)字的字母集合
String[] possibilities = com.get(allNum[index]);
for (int i = 0; i < possibilities.length; i++) {
phoneNumberHelper(result, current.append(possibilities[i]), index + 1, allNum, com);
//一定要把StringBuilder的最后一位刪除掉。
current.deleteCharAt(current.length()-1);
}
}
}
可以看出，回溯的題目并不難，在理解了排列組合題目之后，理解這個就簡單一些了。我們對比一下和排列組合題目的不同。
搜索集合在每一個狀態(tài)都不一樣，排列組合在每個步驟都是相同的搜索集合，電話按鍵根據(jù)按下的數(shù)字不一樣，對應(yīng)的字母不一樣。
對于回溯算法的精髓，大家通過對兩個題目的練習(xí)可以發(fā)現(xiàn)，就在于那個remove的動作，假如上面這個算法我改成這樣，不使用StringBuilder，而直接使用Sting.
public List<String> letterCombinations(String digits) {
if (digits == null || digits.length() == 0) {
return new ArrayList<>();
}
String[] one = { "" };
String[] two = { "a", "b", "c" };
String[] three = { "d", "e", "f" };
String[] four = { "g", "h", "i" };
String[] five = { "j", "k", "l" };
String[] six = { "m", "n", "o" };
String[] seven = { "p", "q", "r", "s" };
String[] eight = { "t", "u", "v" };
String[] nine = { "w", "x", "y", "z" };
String[] zero = { "" };
HashMap<Integer, String[]> map = new HashMap<>();
map.put(0, zero);
map.put(1, one);
map.put(2, two);
map.put(3, three);
map.put(4, four);
map.put(5, five);
map.put(6, six);
map.put(7, seven);
map.put(8, eight);
map.put(9, nine);
ArrayList<String> result = new ArrayList<>();
int[] allNum = new int[digits.length()];
for (int i = 0; i < digits.length(); i++) {
allNum[i] = Integer.parseInt(digits.substring(i, i + 1));
}
phoneNumberHelper(result, "", 0, allNum, map);
return result;
}
private void phoneNumberHelper(ArrayList<String> result, String current, int index, int[] allNum,
HashMap<Integer, String[]> com) {
if (index == allNum.length) {
result.add(current);
return;
} else {
String[] possibilities = com.get(allNum[index]);
for (int i = 0; i < possibilities.length; i++) {
//不使用StringBuilder，直接使用String連接一個String，這個做法其實和new String()是一樣的。創(chuàng)建了一個新的String，
phoneNumberHelper(result, current + possibilities[i], index + 1, allNum, com);
}
}
}
算法大部分都是相同的，但是直接直接使用String連接一個String，這個做法其實和new String()是一樣的。創(chuàng)建了一個新的String，和我們的排列組合里面的new ArrayList<>(temp)這段代碼一樣，雖然最終結(jié)果沒錯，但是卻喪失了回溯算法的本質(zhì)和優(yōu)勢，浪費了空間。一行之差。
4.N皇后問題
這一篇的最后一個問題，當然非N皇后問題莫屬，題目太經(jīng)典，我就不浪費篇幅再寫一次算法了。我這次就著重分析一下這個怎么把這個問題抽象成回溯問題。怎么把這個問題模型化，通俗點說，怎么把這個問題和排列組合問題找到相同的地方，方便大家理解。
我們每一次在棋盤上放棋子，其實就是從原集合，往答案集合中加入元素的一個動作。和排列組合問題不同的是，往答案集合里面加入元素這個動作不是每次都是合法的，而排列組合是無論怎么加都對。
舉個栗子
在放置第五個棋子的時候，我們在遍歷的過程中需要判斷第五個可以合法的放置在哪個位置，第一行？不行，因為第一個棋子也在第一行。第二第三第四同理。都通不過我們的檢查。所以在for循環(huán)中要對之前已經(jīng)放置的棋子做比較，看看能不能放置到我們想放置的位置，如果不行，那么我們需要回退到上一層。
所以N皇后問題最后的難點就在于，怎么表示放置棋子的位置？怎么做所謂的合法檢查？這些大家可以自己思考一下再用java實現(xiàn)一下。
當我以前在復(fù)習(xí)N皇后問題的時候，我有那么一剎那和排列組合問題做了個比較，頓時恍然大悟。原來原理是相同的。
這次的回溯算法的分析就到此位置，下一次我會做一個更全面的深度優(yōu)先的算法分析。
祝大家新年快樂！！
