回溯算法作為一種經(jīng)典的有效的暴力搜索策略。其基本思想是搜索過程中沿著一條路徑一直往前走，當(dāng)探索到某一步時(shí)發(fā)現(xiàn)無法滿足要求時(shí)，則退回到上一步選擇另外一條路徑繼續(xù)往前搜索。對(duì)于許多大規(guī)模復(fù)雜問題而言，很多時(shí)候都可以通過回溯算法嘗試解決

算法模板

結(jié)合LeetCode刷題經(jīng)驗(yàn)，現(xiàn)對(duì)回溯算法的解題思路進(jìn)行總結(jié)，并形成下面的偽代碼模板。我們首先需要兩個(gè)全局變量：result、state。前者用于保存最終搜索結(jié)果；后者用于記錄搜索過程中的狀態(tài)信息。故在程序入口getResult方法中首先需要通過init方法完成全局變量的初始化，最后直接返回全局變量result作為題解即可。而這期間通過search方法進(jìn)行回溯搜索即可

search方法的最重要思路是根據(jù)當(dāng)前狀態(tài)等信息獲取下一步搜索的可選擇空間，即通過調(diào)用getAvailableList方法實(shí)現(xiàn)，然后遍歷該可選擇空間。具體地對(duì)于每個(gè)選擇，先判斷是否符合條件。如果符合，則說明可以選擇它繼續(xù)往前搜索。那么我們第1步先做出選擇，包括對(duì)狀態(tài)變量state的更新；第2步通過遞歸調(diào)用search方法實(shí)現(xiàn)所謂的一直往前搜索；第3步當(dāng)遞歸調(diào)用結(jié)束返回時(shí)則說明已經(jīng)當(dāng)前搜索路徑已經(jīng)退回到上一步了，這個(gè)時(shí)候我們就需要撤銷第1步做出的選擇對(duì)狀態(tài)變量的影響了?？偠灾?，回溯的關(guān)鍵就在于在遞歸搜索之前需要做出選擇，而在遞歸搜索之后需要撤銷選擇

前面提到search方法會(huì)一直遞歸調(diào)用下去。那遞歸終止條件是什么呢？其實(shí)也很簡(jiǎn)單，第一種是發(fā)現(xiàn)不滿足合法條件時(shí)直接return，即所謂的剪枝優(yōu)化；第二種則是搜索成功，此時(shí)需要根據(jù)狀態(tài)等信息將當(dāng)前的搜索結(jié)果添加最終結(jié)果當(dāng)中去

/**
?*?回溯算法模板
?*/
public?static?class?Solution?{
????//?全局變量:?最終結(jié)果
????private?result;

????//?全局變量:?當(dāng)前搜索過程的狀態(tài)信息
????private?state;

????/**
?????*?入口
?????*/
????public?getResult(...)?{
????????//?Step?1:?初始化全局變量
????????init(...);
????????//?Step?2:?回溯法搜索
????????search(...);
????????//?Step?3:?直接返回搜索結(jié)果
????????return?result;
????}

????/**
?????*?初始化全局變量
?????*/
????private?void?init(...)?{
????????result?=?...
????????state?=?...
????}

????/**
?????*?基于回溯算法的搜索
?????*/
????private?void?search(...)?{
????????//?剪枝
????????if(?不滿足合法條件?)?{
????????????return;
????????}?
????????
????????//?搜索成功
????????if(?滿足搜索結(jié)束條件?)?{
????????????//?根據(jù)當(dāng)前狀態(tài)信息,?更新result結(jié)果
????????????...
????????????return;
????????}

????????//?根據(jù)當(dāng)前狀態(tài)獲取選擇列表
????????availableList?=?getAvailableList(...);
????????//?遍歷選擇列表
????????for(int[]?tempIndex?:?availableList)?{
????????????if(?判斷當(dāng)前選擇?是否滿足?合法條件?)?{
????????????????//?1.?做選擇:?更新狀態(tài)信息
????????????????...
????????????????//?2.?遞歸搜索下一步
????????????????search(...)
????????????????//?3.?撤銷選擇:?撤銷對(duì)狀態(tài)信息的修改操作
????????????????...

????????????}
????????}
????}

????/**
?????*?根據(jù)當(dāng)前狀態(tài)獲取選擇列表
?????*/
????private?getAvailableList(...)?{
????????...
????}
}

實(shí)踐

LeetCode: 17. 電話號(hào)碼的字母組合

這里以 LeetCode 第17題 <電話號(hào)碼的字母組合> 為具體示例來進(jìn)行闡述

給定一個(gè)僅包含數(shù)字 2-9 的字符串，返回所有它能表示的字母組合。答案可以按 任意順序 返回。數(shù)字到字母的映射如下圖（與電話按鍵相同），注意1不對(duì)應(yīng)任何字母

示例 1：?

輸入：digits = "23"?

輸出：["ad","ae","af","bd","be","bf","cd","ce","cf"]

示例 2：?

輸入：digits = ""?

輸出：[]

示例 3：?

輸入：digits = "2"?

輸出：["a","b","c"]

按照模板則解法如下所示。由于本題在搜索過程中，任意一個(gè)搜索都是合法的，故不需要判斷每次選擇的合法性，直接按照 “做出選擇-遞歸搜索下一個(gè)-撤銷選擇” 的思路進(jìn)行處理即可

/**
?*?回溯法
?*/
public?static?class?Solution?{
????/**
?????*?數(shù)字與字符的映射,?key:?數(shù)字,?value:?字母
?????*/
????private?static??Map?num2StringMap;

????static?{
????????num2StringMap?=?new?HashMap<>();
????????num2StringMap.put('2',?"abc");
????????num2StringMap.put('3',?"def");
????????num2StringMap.put('4',?"ghi");
????????num2StringMap.put('5',?"jkl");
????????num2StringMap.put('6',?"mno");
????????num2StringMap.put('7',?"pqrs");
????????num2StringMap.put('8',?"tuv");
????????num2StringMap.put('9',?"wxyz");
????}

????/**
?????*?最終結(jié)果:?字母組合列表
?????*/
????private?List?result;

????/**
?????*?狀態(tài)變量：當(dāng)前搜索結(jié)果
?????*/
????private?StringBuilder?sb;

????public?List?letterCombinations(String?digits)?{
????????//?判空
????????if(?digits==null?||?digits.length()==0?)?{
????????????return?Collections.emptyList();
????????}

????????//?初始化全局變量
????????init();
????????//?從第0個(gè)數(shù)開始搜索
????????search(digits,?0);
????????//?直接返回最終搜索結(jié)果
????????return?result;
????}

????/**
?????*?初始化全局變量
?????*/
????private?void?init()?{
????????result?=?new?LinkedList<>();
????????sb?=?new?StringBuilder();
????}

????/**
?????*?回溯法遞歸搜索
?????*?@param?digits?待搜索數(shù)字
?????*?@param?index?搜索第index個(gè)數(shù)字
?????*/
????private?void?search(String?digits,?int?index)?{
????????//?數(shù)字全部搜索結(jié)束
????????if(?index?==?digits.length()?)?{
????????????//?將當(dāng)前搜索結(jié)果加入最終結(jié)果集
????????????result.add(?sb.toString()?);
????????????return;
????????}

????????//?獲取第index個(gè)數(shù)字的可選擇字符
????????char?num?=?digits.charAt(index);
????????String?choice?=?getChooseList(num);
????????//?遍歷可選擇字符
????????for(char?ch?:?choice.toCharArray()?)?{
????????????//?將當(dāng)前字符加入搜索結(jié)果
????????????sb.append(?ch?);
????????????//?遞歸搜索下一個(gè)數(shù)字
????????????search(digits,?index+1);
????????????//?將當(dāng)前字符從搜索結(jié)果中移除,?即撤銷所做出的選擇,?以進(jìn)行for循環(huán)的下一次遍歷
????????????sb.deleteCharAt(?sb.length()-1?);
????????}
????}

????/**
?????*?當(dāng)前數(shù)字的可選擇字符
?????*?@param?ch
?????*?@return
?????*/
????private?String?getChooseList(char?ch)?{
????????return?num2StringMap.get(ch);
????}
}

LeetCode: 51. N皇后

這里以 LeetCode 第51題 為具體示例來進(jìn)行闡述

n 皇后問題 研究的是如何將 n 個(gè)皇后放置在 n×n 的棋盤上，并且使皇后彼此之間不能相互攻擊。給你一個(gè)整數(shù) n ，返回所有不同的 n 皇后問題 的解決方案。每一種解法包含一個(gè)不同的 n 皇后問題 的棋子放置方案，該方案中 'Q' 和 '.' 分別代表了皇后和空位

示例 1：?

輸入：n = 4?

輸出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]?

解釋：如下圖所示，4皇后問題存在兩個(gè)不同的解法

示例 2：?

輸入：n = 1?

輸出：[["Q"]]

按照模板則解法如下所示。本題中對(duì)于皇后的放置位置有一定要求，棋盤中的行、列、斜線不同同時(shí)放置兩個(gè)皇后，故在遍歷時(shí)通過isValid方法保證當(dāng)前選擇的合法

public?static?class?Solution?{
????/**
?????*?最終結(jié)果：所有N皇后問題的解決方案
?????*/
????private?List>?result;

????/**
?????*?狀態(tài)變量：n*n的棋盤布局, true:?表示相應(yīng)網(wǎng)格放置了皇后, false:?表示相應(yīng)網(wǎng)格未放置皇后
?????*/
????private?Boolean[][]?board;

????public?List>?solveNQueens(int?n)?{
????????init(n);
????????//?從第0行開始放置皇后
????????search(n,?0);
????????return?result;
????}

????/**
?????*?全局變量初始化
?????*?@param?n
?????*/
????private?void?init(int?n)?{
????????result?=?new?LinkedList<>();
????????board?=?new?Boolean[n][n];
????????for(int?i=0;?i????????????Arrays.fill(?board[i],?false?);
????????}
????}

????/**
?????*?遞歸法搜索
?????*?@param?n
?????*?@param?rowIndex?放置第rowIndex行的皇后
?????*/
????private?void?search(int?n,?int?rowIndex)?{
????????//?N個(gè)皇后全部放置完畢
????????if(rowIndex?==?n)?{
????????????//?將狀態(tài)變量轉(zhuǎn)換為棋盤布局,?并添加到最終結(jié)果當(dāng)中
????????????convert();
????????????return;
????????}

????????for(int?colIndex=0;?colIndex????????????if(?isValid(rowIndex,?colIndex)?)?{
????????????????board[rowIndex][colIndex]?=?true;
????????????????search(n,?rowIndex+1);
????????????????board[rowIndex][colIndex]?=?false;
????????????}
????????}

????}

????/**
?????*?判斷選擇的合法性
?????*?@param?rowIndex
?????*?@param?colIndex
?????*?@return
?????*/
????private?boolean?isValid(int?rowIndex,?int?colIndex)?{
????????//?所在列不能有皇后
????????for(int?i=0;?i????????????if(?board[i][colIndex])?{
????????????????return?false;
????????????}
????????}

????????//?所在主斜線的左上方部分不能有皇后
????????for(int?i=1;;i++)?{
????????????//?主斜線左上角的網(wǎng)格
????????????int?x1?=?rowIndex?-?i;
????????????int?y1?=?colIndex?-?i;
????????????//?網(wǎng)格均不在棋盤范圍內(nèi)
????????????if(?x1<0?||?y1<0?)?{
????????????????break;
????????????}
????????????//?存在包含皇后的網(wǎng)格
????????????if(?board[x1][y1]?)?{
????????????????return?false;
????????????}
????????}

????????//?所在次斜線的右上方部分不能有皇后
????????for(int?i=1;;?i++)?{
????????????int?x1?=?rowIndex?-?i;
????????????int?y1?=?colIndex?+?i;
????????????if(?x1<0?||?y1>board.length-1?)?{
????????????????break;
????????????}
????????????if(?board[x1][y1]?)?{
????????????????return?false;
????????????}
????????}

????????return?true;
????}

????/**
?????*?將狀態(tài)變量轉(zhuǎn)換為棋盤布局,?并添加到最終結(jié)果當(dāng)中
?????*/
????private?void?convert()?{
????????List?tempList?=?new?LinkedList<>();
????????for(int?i=0;?i????????????String?rowStr?=?Arrays.stream(?board[i]?)
????????????????.map(?e?->?{
????????????????????//?true:?表示相應(yīng)網(wǎng)格放置了皇后
????????????????????if(?e?)?{
????????????????????????return?"Q";
????????????????????}
????????????????????//?false:?表示相應(yīng)網(wǎng)格未放置皇后
????????????????????return?".";
????????????????}?)
????????????????.collect(Collectors.joining());
????????????tempList.add(?rowStr?);
????????}
????????result.add(?tempList?);
????}

}

劍指Offer(第2版): 12. 矩陣中的路徑

這里以 LeetCode 的劍指Offer(第2版)題單中的第12題 <矩陣中的路徑> 為具體示例來進(jìn)行闡述

給定一個(gè) m x n 二維字符網(wǎng)格 board 和一個(gè)字符串單詞 word 。如果 word 存在于網(wǎng)格中，返回 true ；否則，返回 false 。單詞必須按照字母順序，通過相鄰的單元格內(nèi)的字母構(gòu)成，其中“相鄰”單元格是那些水平相鄰或垂直相鄰的單元格。同一個(gè)單元格內(nèi)的字母不允許被重復(fù)使用

例如，在下面的 3×4 的矩陣中包含單詞 "ABCCED"（單詞中的字母已標(biāo)出）。

示例 1：?

輸入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"?

輸出：true

示例 2：?

輸入：board = [["a","b"],["c","d"]], word = "abcd"?

輸出：false

按照模板則解法如下所示。一方面本題每次的搜索路徑為上、下、左、右這四個(gè)方向上未使用過的網(wǎng)絡(luò)；另一方面本題只需判斷能夠搜索成功即可。所以當(dāng)?shù)谝淮嗡阉鞒晒?，即可以不再進(jìn)行搜索。故解法中加入了基于exist結(jié)果判斷的剪枝優(yōu)化

/**
?*?回溯法
?*/
public?static?class?Solution?{
????/**
?????*?行數(shù)
?????*/
????private?int?row;

????/**
?????*?列數(shù)
?????*/
????private?int?col;

????/**
?????*?最終結(jié)果標(biāo)記,?true:?找到;?false:?未找到
?????*/
????private?boolean?exist;

????/**
?????*?網(wǎng)格被訪問狀態(tài)標(biāo)記,?true:?該元素被訪問;?false:?該元素未被訪問
?????*/
????private?boolean[][]?usedArray;

????public?boolean?exist(char[][]?board,?String?word)?{
????????if(?board==null?||?board[0]==null?||?word==null?||?word==""?//?判空
????????????||?board.length*board[0].length?//?剪枝:?網(wǎng)格元素?cái)?shù)小于字符串?dāng)?shù)量,?肯定搜索不到
????????????return?false;
????????}

????????//?初始化全局變量
????????init(board,?word);
????????//?從字符串的第一個(gè)字符開始搜索
????????search(board,?word,?0,?0,?0);
????????return?exist;
????}

????/**
?????*?初始化全局變量
?????*?@param?board
?????*?@param?word
?????*/
????public?void?init(char[][]?board,?String?word)?{
????????exist?=?false;
????????row?=?board.length;
????????col?=?board[0].length;
????????usedArray?=?new?boolean[row][col];
????}

????/**
?????*?回溯法搜索
?????*?@param?board?網(wǎng)格
?????*?@param?word??字符串
?????*?@param?index?搜字符串的第index個(gè)字符
?????*?@param?i?網(wǎng)格元素的橫坐標(biāo)
?????*?@param?j?網(wǎng)格元素的縱坐標(biāo)
?????*/
????public?void?search(char[][]?board,?String?word,?int?index,?int?i,?int?j)?{
????????//?剪枝:?只要有一次搜索成功了即可結(jié)束搜索任務(wù)
????????if(?exist?)?{
????????????//?剪枝
????????????return;
????????}?else?if(?index?==?word.length()?)?{
????????????//?搜索成功,?更新結(jié)果,?并結(jié)束
????????????exist?=?true;
????????????return;
????????}

????????//?獲取選擇空間
????????Set<int[]>?indexSet?=?getAvailableIndexSet(index,?i,?j);
????????//?遍歷選擇空間
????????for(int[]?tempIndex?:?indexSet)?{

????????????//?剪枝:?只要有一次搜索成功了即可結(jié)束搜索任務(wù)
????????????if(exist)?{
????????????????break;
????????????}

????????????int?rowIndex?=?tempIndex[0];
????????????int?colIndex?=?tempIndex[1];
????????????//?字符串的第index個(gè)元素搜索成功
????????????if(?board[rowIndex][colIndex]?==?word.charAt(index)?)?{
????????????????//?將網(wǎng)格中相應(yīng)的元素標(biāo)記為?被訪問狀態(tài)
????????????????usedArray[rowIndex][colIndex]?=?true;
????????????????//?遞歸搜索字符串中的下一個(gè)元素
????????????????search(?board,?word,?index+1,?rowIndex,?colIndex);
????????????????//?將網(wǎng)格中相應(yīng)的元素標(biāo)記為?未被訪問狀態(tài),?即撤銷所做出的選擇,?以進(jìn)行for循環(huán)的下一次遍歷
????????????????usedArray[rowIndex][colIndex]?=?false;
????????????}
????????}
????}

????/**
?????*?獲取當(dāng)前網(wǎng)格元素的可選擇列表
?????*?@param?index
?????*?@param?i
?????*?@param?j
?????*?@return
?????*/
????public?Set<int[]>?getAvailableIndexSet(int?index,?int?i,?int?j)?{
????????//?自定義比較器:?當(dāng)兩個(gè)數(shù)組類型的元素,?如果數(shù)組中的內(nèi)容均相同則視為同一元素
????????Set<int[]>?indexSet?=?new?TreeSet<>(?(a1,?a2)?->?{
????????????if(?a1[0]?==?a2[0]?&&?a1[1]?==?a2[1]?)?{
????????????????return?0;
????????????}
????????????return?1;
????????});

????????//?搜索字符串第一個(gè)字符時(shí),?則可選擇的空間是整個(gè)網(wǎng)格
????????if(?index?==?0?)?{
????????????for(int?rowIndex=0;?rowIndex????????????????for?(int?colIndex=0;?colIndex????????????????????int[]?tempIndex?=?new?int[]{rowIndex,?colIndex};
????????????????????indexSet.add(?tempIndex?);
????????????????}
????????????}
????????????return?indexSet;
????????}

????????//?搜索字符串不是第一個(gè)字符時(shí),?則可選擇的空間是當(dāng)前網(wǎng)絡(luò)元素(i,j)的上、下、左、右這四個(gè)元素
????????int?iMax?=?i+1?<=?row-1???i+1?:?row-1;
????????int?iMin?=?i-1?>=?0???i-1?:?0;
????????int?jMax?=?j+1?<=?col-1???j+1?:?col-1;
????????int?jMin?=?j-1?>=?0???j-1?:?0;
????????indexSet.add(?new?int[]{iMin,?j}?);
????????indexSet.add(?new?int[]{iMax,?j}?);
????????indexSet.add(?new?int[]{i,?jMin}?);
????????indexSet.add(?new?int[]{i,?jMax}?);

????????//?選擇空間中的元素需要移除掉已經(jīng)被訪問過的
????????indexSet.removeIf(?tempIndex?->?{
????????????int?rowIndex?=?tempIndex[0];
????????????int?colIndex?=?tempIndex[1];
????????????return?usedArray[rowIndex][colIndex];
????????}?);

????????return?indexSet;
????}

}

劍指Offer(第2版): 13. 機(jī)器人的運(yùn)動(dòng)范圍

這里以 LeetCode 的劍指Offer(第2版)題單中的第13題 <機(jī)器人的運(yùn)動(dòng)范圍> 為具體示例來進(jìn)行闡述

地上有一個(gè)m行n列的方格，從坐標(biāo) [0,0] 到坐標(biāo) [m-1,n-1] 。一個(gè)機(jī)器人從坐標(biāo) [0, 0] 的格子開始移動(dòng)，它每次可以向左、右、上、下移動(dòng)一格（不能移動(dòng)到方格外），也不能進(jìn)入行坐標(biāo)和列坐標(biāo)的數(shù)位之和大于k的格子。例如，當(dāng)k為18時(shí)，機(jī)器人能夠進(jìn)入方格 [35, 37] ，因?yàn)?+5+3+7=18。但它不能進(jìn)入方格 [35, 38]，因?yàn)?+5+3+8=19。請(qǐng)問該機(jī)器人能夠到達(dá)多少個(gè)格子？

示例 1：?

輸入：m = 2, n = 3, k = 1?

輸出：3

示例 2：?

輸入：m = 3, n = 1, k = 0?

輸出：1

按照模板則解法如下所示。一方面本題每次的搜索路徑為下、右這兩個(gè)方向上未使用過的網(wǎng)絡(luò)；另一方面本題要求的是統(tǒng)計(jì)機(jī)器人可以進(jìn)入的方格總數(shù)。故每進(jìn)入一個(gè)有效方格時(shí)，需要更新統(tǒng)計(jì)值，并將該方格標(biāo)記為已訪問過。但需要注意的是本題在回溯之后，即遞歸返回后不需要撤銷所做出的選擇。即不能再將之前已經(jīng)訪問的方格從已訪問的狀態(tài)撤銷為未訪問的狀態(tài)。否則即會(huì)導(dǎo)致重復(fù)統(tǒng)計(jì)。換言之，在實(shí)際解題過程中不能生搬硬套解題模板。要善于理論聯(lián)系實(shí)際、靈活應(yīng)變。解題模板的作用在于總結(jié)經(jīng)驗(yàn)、沉淀認(rèn)知、減少解題的思維負(fù)擔(dān)，它并不能完全取代、代替整個(gè)思考過程

class?Solution?{
????/**
?????*?結(jié)果變量:?統(tǒng)計(jì)數(shù)
?????*/
????private?int?result;

????/**
?????*?狀態(tài)變量:?方格訪問標(biāo)記
?????*/????
????private?boolean[][]?usedFlag;

????/**
?????*?方向向量:?向右、向下
?????*/
????private?int[]?dx?=?new?int[]{0,1};
????private?int[]?dy?=?new?int[]{1,0};

????public?int?movingCount(int?m,?int?n,?int?k)?{
????????if(?k<0?)?{
????????????return?0;
????????}

????????init(m,?n);
????????search(k,?0,?0);
????????return?result;
????}

????private?void?init(int?m,?int?n)?{
????????usedFlag?=?new?boolean[m][n];
????????//?起點(diǎn)(0,0)是合法的
????????usedFlag[0][0]?=?true;
????????result?=?1;
????}

????private?void?search(int?k,?int?rowIndex,?int?colIndex)?{
????????//?遍歷可選路徑
????????for(int?i=0;?i<2;?i++)?{
????????????//?計(jì)算可選路徑的坐標(biāo)
????????????int?nextRowIndex?=?rowIndex?+?dx[i];
????????????int?nextColIndex?=?colIndex?+?dy[i];

????????????//?滿足搜索條件
????????????if(?nextRowIndex>=0?&&?nextRowIndex<=usedFlag.length-1
????????????????&&?nextColIndex>=0?&&?nextColIndex<=usedFlag[0].length-1
????????????????&&?calcSum(nextRowIndex,?nextColIndex)<=k?&&?!usedFlag[nextRowIndex][nextColIndex]?)?{
????????????????//?更新計(jì)數(shù)值到結(jié)果變量
????????????????result++;
????????????????//?更新狀態(tài)變量,?將其設(shè)置為已訪問
????????????????usedFlag[nextRowIndex][nextColIndex]?=?true;
????????????????//?向下或向右繼續(xù)搜索
????????????????search(k,?nextRowIndex,?nextColIndex);
????????????}
????????}
????}

????/**
?????*?計(jì)算兩個(gè)數(shù)的數(shù)位之和
?????*?@param?num1
?????*?@param?num2
?????*?@return
?????*/
????private?int?calcSum(int?num1,?int?num2)?{
????????int?sum?=?0;
????????while(?num1!=0?)?{
????????????sum?+=?num1?%?10;???//?取個(gè)位進(jìn)行求和
????????????num1?=?num1?/?10;???//?移除個(gè)位
????????}
????????while(?num2!=0?)?{
????????????sum?+=?num2?%?10;
????????????num2?=?num2?/?10;
????????}
????????return?sum;
????}
}