理論基礎(chǔ)

什么是回溯法？
回溯法也可以叫做回溯搜索法，它是一種搜索的方式。

在二叉樹系列中，我們已經(jīng)不止一次，提到了回溯，例如二叉樹：以為使用了遞歸，其實(shí)還隱藏著回溯。
回溯是遞歸的副產(chǎn)品，只要有遞歸就會(huì)有回溯。

所以以下講解中，回溯函數(shù)也就是遞歸函數(shù)，指的都是一個(gè)函數(shù)。

回溯法的效率

回溯法的性能如何呢，這里要和大家說清楚了，雖然回溯法很難，很不好理解，但是回溯法并不是什么高效的算法。
因?yàn)榛厮莸谋举|(zhì)是窮舉，窮舉所有可能，然后選出我們想要的答案，如果想讓回溯法高效一些，可以加一些剪枝的操作，但也改不了回溯法就是窮舉的本質(zhì)。

那么既然回溯法并不高效為什么還要用它呢？
因?yàn)闆]得選，一些問題能暴力搜出來就不錯(cuò)了，撐死了再剪枝一下，還沒有更高效的解法。

那么都什么問題，這么牛逼，只能暴力搜索。

回溯法解決的問題

回溯法，一般可以解決如下幾種問題：

組合問題：N個(gè)數(shù)里面按一定規(guī)則找出k個(gè)數(shù)的集合
切割問題：一個(gè)字符串按一定規(guī)則有幾種切割方式
子集問題：一個(gè)N個(gè)數(shù)的集合里有多少符合條件的子集
排列問題：N個(gè)數(shù)按一定規(guī)則全排列，有幾種排列方式
棋盤問題：N皇后，解數(shù)獨(dú)等等

回溯法模板

卡哥總結(jié)的回溯算法模板。

回溯三部曲：

1.回溯函數(shù)模板返回值以及參數(shù)：回溯算法中函數(shù)返回值一般為void。再來看一下參數(shù)，因?yàn)榛厮菟惴ㄐ枰膮?shù)可不像二叉樹遞歸的時(shí)候那么容易一次性確定下來，所以一般是先寫邏輯，然后需要什么參數(shù)，就填什么參數(shù)。

回溯函數(shù)偽代碼如下：

void backtracking(參數(shù))

2.回溯函數(shù)終止條件：
什么時(shí)候達(dá)到了終止條件，樹中就可以看出，一般來說搜到葉子節(jié)點(diǎn)了，也就找到了滿足條件的一條答案，把這個(gè)答案存放起來，并結(jié)束本層遞歸。

所以回溯函數(shù)終止條件偽代碼如下：

if (終止條件) {存放結(jié)果;return;
}

3.回溯搜索的遍歷過程：
在上面我們提到了，回溯法一般是在集合中遞歸搜索，集合的大小構(gòu)成了樹的寬度，遞歸的深度構(gòu)成的樹的深度。

回溯函數(shù)遍歷過程偽代碼如下：

for (選擇：本層集合中元素（樹中節(jié)點(diǎn)孩子的數(shù)量就是集合的大小）) {處理節(jié)點(diǎn);backtracking(路徑，選擇列表); // 遞歸回溯，撤銷處理結(jié)果
}

for循環(huán)可以理解是橫向遍歷，backtracking（遞歸）就是縱向遍歷，這樣就把這棵樹全遍歷完了，一般來說，搜索葉子節(jié)點(diǎn)就是找的其中一個(gè)結(jié)果了。

組合

力扣題目鏈接

給定兩個(gè)整數(shù) n 和 k，返回 1 … n 中所有可能的 k 個(gè)數(shù)的組合。

示例: 輸入: n = 4, k = 2 輸出: [ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4], ]

思路

可以看出這棵樹，一開始集合是 1，2，3，4， 從左向右取數(shù)，取過的數(shù)，不再重復(fù)取。

第一次取1，集合變?yōu)?，3，4 ，因?yàn)閗為2，我們只需要再取一個(gè)數(shù)就可以了，分別取2，3，4，得到集合[1,2] [1,3] [1,4]，以此類推。

每次從集合中選取元素，可選擇的范圍隨著選擇的進(jìn)行而收縮，調(diào)整可選擇的范圍。

圖中可以發(fā)現(xiàn)n相當(dāng)于樹的寬度，k相當(dāng)于樹的深度。

那么如何在這個(gè)樹上遍歷，然后收集到我們要的結(jié)果集呢？

圖中每次搜索到了葉子節(jié)點(diǎn)，我們就找到了一個(gè)結(jié)果。

相當(dāng)于只需要把達(dá)到葉子節(jié)點(diǎn)的結(jié)果收集起來，就可以求得 n個(gè)數(shù)中k個(gè)數(shù)的組合集合。

回溯法三部曲

遞歸函數(shù)的返回值以及參數(shù)
在這里要定義兩個(gè)全局變量，一個(gè)用來存放符合條件單一結(jié)果，一個(gè)用來存放符合條件結(jié)果的集合。

vector<vector<int>> result; // 存放符合條件結(jié)果的集合
vector<int> path; // 用來存放符合條件結(jié)果

函數(shù)里一定有兩個(gè)參數(shù)，既然是集合n里面取k個(gè)數(shù)，那么n和k是兩個(gè)int型的參數(shù)。

然后還需要一個(gè)參數(shù)，為int型變量startIndex，這個(gè)參數(shù)用來記錄本層遞歸中，集合從哪里開始遍歷（集合就是[1,…,n] ）。

為什么要有這個(gè)startIndex呢？
startIndex 就是防止出現(xiàn)重復(fù)的組合。
從下圖中紅線部分可以看出，在集合[1,2,3,4]取1之后，下一層遞歸，就要在[2,3,4]中取數(shù)了，那么下一層遞歸如何知道從[2,3,4]中取數(shù)呢，靠的就是startIndex。

所以需要startIndex來記錄下一層遞歸，搜索的起始位置。

那么整體代碼如下：

vector<vector<int>> result; // 存放符合條件結(jié)果的集合
vector<int> path; // 用來存放符合條件單一結(jié)果
void backtracking(int n, int k, int startIndex)

回溯函數(shù)終止條件
什么時(shí)候到達(dá)所謂的葉子節(jié)點(diǎn)了呢？

path這個(gè)數(shù)組的大小如果達(dá)到k，說明我們找到了一個(gè)子集大小為k的組合了，在圖中path存的就是根節(jié)點(diǎn)到葉子節(jié)點(diǎn)的路徑。
此時(shí)用result二維數(shù)組，把path保存起來，并終止本層遞歸。

所以終止條件代碼如下：

if (path.size() == k) {result.push_back(path);return;
}

單層搜索的過程
回溯法的搜索過程就是一個(gè)樹型結(jié)構(gòu)的遍歷過程，在如下圖中，可以看出for循環(huán)用來橫向遍歷，遞歸的過程是縱向遍歷。

如此我們才遍歷完圖中的這棵樹。
for循環(huán)每次從startIndex開始遍歷，然后用path保存取到的節(jié)點(diǎn)i。
可以看出backtracking（遞歸函數(shù)）通過不斷調(diào)用自己一直往深處遍歷，總會(huì)遇到葉子節(jié)點(diǎn)，遇到了葉子節(jié)點(diǎn)就要返回。
backtracking的下面部分就是回溯的操作了，撤銷本次處理的結(jié)果。

代碼如下：

for (int i = startIndex; i <= n; i++) { // 控制樹的橫向遍歷path.push_back(i); // 處理節(jié)點(diǎn)backtracking(n, k, i + 1); // 遞歸：控制樹的縱向遍歷，注意下一層搜索要從i+1開始path.pop_back(); // 回溯，撤銷處理的節(jié)點(diǎn)
}

代碼

class Solution {
public:vector<int> paths;vector<vector<int>>result;void backtracking(int n , int k ,int startidx){if(paths.size()==k){result.push_back(paths);return;}   for(int i = startidx;i <= n ;i++){paths.push_back(i);backtracking(n,k,i+1);paths.pop_back();}}vector<vector<int>> combine(int n, int k) {backtracking(n,k,1);return result;}
};

組合（優(yōu)化）

組合總和III

力扣題目鏈接

找出所有相加之和為 n 的 k 個(gè)數(shù)的組合。組合中只允許含有 1 - 9 的正整數(shù)，并且每種組合中不存在重復(fù)的數(shù)字。

說明：
所有數(shù)字都是正整數(shù)。
解集不能包含重復(fù)的組合。

示例 1: 輸入: k = 3, n = 7 輸出: [[1,2,4]]

思路

代碼

class Solution {
public:vector<vector<int>>result;vector<int>paths;int sum = 0;void backtracking(int n , int k,int startidx){if(paths.size()>k) return;if(sum > n) return;if(paths.size()==k && sum==n ){result.push_back(paths);return ;}for(int i = startidx; i<=9;++i){paths.push_back(i);sum+=i;backtracking(n,k,i+1);paths.pop_back();sum-=i;}}vector<vector<int>> combinationSum3(int k, int n) {backtracking(n,k,1);return result;}
};

電話號(hào)碼的字母組合

力扣題目鏈接

給定一個(gè)僅包含數(shù)字 2-9 的字符串，返回所有它能表示的字母組合。

給出數(shù)字到字母的映射如下（與電話按鍵相同）。注意 1 不對(duì)應(yīng)任何字母。

示例 ：
輸入：digits = “23”
輸出：[“ad”,“ae”,“af”,“bd”,“be”,“bf”,“cd”,“ce”,“cf”]

思路

數(shù)字和字母如何映射
可以使用map或者定義一個(gè)二維數(shù)組，例如：string letterMap[10]，來做映射，我這里定義一個(gè)二維數(shù)組，代碼如下：

const string letterMap[10] = {"", // 0"", // 1"abc", // 2"def", // 3"ghi", // 4"jkl", // 5"mno", // 6"pqrs", // 7"tuv", // 8"wxyz", // 9
};

回溯法來解決n個(gè)for循環(huán)的問題

例如：輸入：“23”，抽象為樹形結(jié)構(gòu)，如圖所示：

圖中可以看出遍歷的深度，就是輸入"23"的長度，而葉子節(jié)點(diǎn)就是我們要收集的結(jié)果，輸出[“ad”, “ae”, “af”, “bd”, “be”, “bf”, “cd”, “ce”, “cf”]。

回溯三部曲

確定回溯函數(shù)參數(shù)

首先需要一個(gè)字符串s來收集葉子節(jié)點(diǎn)的結(jié)果，然后用一個(gè)字符串?dāng)?shù)組result保存起來，這兩個(gè)變量我依然定義為全局。
再來看參數(shù)，參數(shù)指定是有題目中給的string digits，然后還要有一個(gè)參數(shù)就是int型的index。
這個(gè)index是記錄遍歷第幾個(gè)數(shù)字了，就是用來遍歷digits的（題目中給出數(shù)字字符串），同時(shí)index也表示樹的深度。

代碼如下：

vector<string> result;
string s;
void backtracking(const string& digits, int index)

確定終止條件
例如輸入用例"23"，兩個(gè)數(shù)字，那么根節(jié)點(diǎn)往下遞歸兩層就可以了，葉子節(jié)點(diǎn)就是要收集的結(jié)果集。

那么終止條件就是如果index 等于 輸入的數(shù)字個(gè)數(shù)（digits.size）了（本來index就是用來遍歷digits的）。

然后收集結(jié)果，結(jié)束本層遞歸。

代碼如下：

if (index == digits.size()) {result.push_back(s);return;
}

這里index跳出循環(huán)后的大小就是數(shù)組的大小

確定單層遍歷邏輯

首先要取index指向的數(shù)字，并找到對(duì)應(yīng)的字符集（手機(jī)鍵盤的字符集）。

然后for循環(huán)來處理這個(gè)字符集，代碼如下：

int digit = digits[index] - '0';        // 將index指向的數(shù)字轉(zhuǎn)為int
string letters = letterMap[digit];      // 取數(shù)字對(duì)應(yīng)的字符集
for (int i = 0; i < letters.size(); i++) {s.push_back(letters[i]);            // 處理backtracking(digits, index + 1);    // 遞歸，注意index+1，一下層要處理下一個(gè)數(shù)字了s.pop_back();                       // 回溯
}

注意這里for循環(huán)，可不像是在回溯算法：求組合問題和回溯算法：求組合總和中從startIndex開始遍歷的。

因?yàn)楸绢}每一個(gè)數(shù)字代表的是不同集合，也就是求不同集合之間的組合，而上述兩道題都是求同一個(gè)集合中的組合！

代碼

class Solution {
public:const vector<string>phones = {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};vector<string>result;string path;void backtracking(string digits , int index){if( index == digits.size()){result.push_back(path);return;}int num = digits[index] - '0';string words = phones[num];for(int i = 0 ; i < words.size();++i){path.push_back(words[i]);backtracking(digits,index+1);path.pop_back();}}vector<string> letterCombinations(string digits) {if(digits.size()==0)return result;backtracking(digits,0);return result;}
};

組合總和

力扣題目鏈接

給定一個(gè)無重復(fù)元素的數(shù)組 candidates 和一個(gè)目標(biāo)數(shù) target ，找出 candidates 中所有可以使數(shù)字和為 target 的組合。
candidates 中的數(shù)字可以無限制重復(fù)被選取。

說明：
所有數(shù)字（包括 target）都是正整數(shù)。
解集不能包含重復(fù)的組合。
示例 1：

輸入：candidates = [2,3,6,7], target = 7,
所求解集為： [ [7], [2,2,3] ]

思路

代碼

class Solution {
public:vector<vector<int>>result;vector<int>paths;void backtracking(vector<int>& candidates , int target ,int sum , int startidx){if(sum > target){return;}if(sum == target){result.push_back(paths);return ;}for(int i = startidx ; i < candidates.size();++i){paths.push_back(candidates[i]);sum += candidates[i];backtracking(candidates,target,sum,i);sum -= candidates[i];paths.pop_back();}}vector<vector<int>> combinationSum(vector<int>& candidates, int target) {backtracking(candidates,target,0,0);return result;}
};

組合總和II

力扣題目鏈接

給定一個(gè)數(shù)組 candidates 和一個(gè)目標(biāo)數(shù) target ，找出 candidates 中所有可以使數(shù)字和為 target 的組合。

candidates 中的每個(gè)數(shù)字在每個(gè)組合中只能使用一次。

說明： 所有數(shù)字（包括目標(biāo)數(shù)）都是正整數(shù)。解集不能包含重復(fù)的組合。

示例 1:
輸入: candidates = [10,1,2,7,6,1,5], target = 8,
所求解集為:

[[1, 7],[1, 2, 5],[2, 6],[1, 1, 6]
]

思路

如果 candidates 中有重復(fù)元素，可能會(huì)生成重復(fù)的組合。為了避免這種情況，首先需要對(duì) candidates 進(jìn)行排序。排序后，相同的數(shù)字會(huì)排列在一起，從而可以更容易地跳過重復(fù)的組合。

不排序去重：

代碼

class Solution {
public:vector<vector<int>>result;vector<int>path;void backtracking(vector<int>& candidates, int target, int sum,int startidx ){if(sum > target)return;if(sum==target){result.push_back(path);return;}for(int i = startidx;i<candidates.size();++i){if(i>startidx && candidates[i]==candidates[i-1])continue;path.push_back(candidates[i]);sum += candidates[i];backtracking(candidates,target,sum,i+1);sum -= candidates[i];path.pop_back();}}vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {sort(candidates.begin(),candidates.end());backtracking(candidates,target,0,0);return result;}
};