摘要
- 回溯和遞歸是相輔相成的，用到回溯的地方一般都會有遞歸丢胚。遞歸是實現(xiàn)回溯的基本方法翩瓜。
- 回溯法并不是很高效的算法，是一種暴力枚舉法携龟，通過枚舉可能答案來解決問題兔跌。
- 回溯法提供了一種枚舉各種可能性的方法，讓一些難以用多層循環(huán)搜索答案的問題至少能用回溯法解決峡蟋，如組合問題和切割問題坟桅。
- 所有的回溯法的問題都可以抽象為樹形結(jié)構(gòu)，即可能答案的構(gòu)造是樹形的蕊蝗。
回溯法基礎(chǔ)
相關(guān)定義和概念
- 定義：回溯法也可以叫做回溯搜索法仅乓，是一種搜索的方式。
- 組合：可以理解為數(shù)學(xué)上的集合蓬戚，并不強調(diào)元素的順序和相對位置夸楣。
- 排列：可以理解為數(shù)學(xué)上的數(shù)列，強調(diào)元素的順序。
回溯法的意義
- 回溯法的本質(zhì)是窮舉豫喧，窮舉所有可能的答案石洗，然后驗證這些答案是否符合題目要求，選出合適的答案紧显。
- 有一些問題只能用回溯法解決讲衫，目前并沒有更高效的解法。
回溯法的理解
- 可能答案的枚舉過程是樹形的鸟妙，可以通過畫出答案的構(gòu)造樹來幫助思考焦人。
- 回溯法的過程都可以抽象為N叉樹挥吵。
- 回溯法解決的問題是在給定集合中遞歸查找子集重父，集合的大小決定了答案樹的寬度（一個節(jié)點有幾個孩子），遞歸的深度構(gòu)成了答案樹的深度忽匈。
- 遞歸用于向下找房午，循環(huán)用于在同一層中找
遞歸與循環(huán)
回溯法的模板
- 回溯法的遞歸函數(shù)一般沒有返回值。
- 遞歸函數(shù)一般命名為
backtracking丹允。 - 回溯法的參數(shù)列表在一開始是不好確定的郭厌，會在分析問題的過程中逐漸完善。
- 先寫遞歸的終止條件雕蔽，在終止條件下收集結(jié)果折柠。
- 然后寫單層搜索的邏輯，一般情況下是
for循環(huán)批狐，用來處理當(dāng)前集合里的每一個元素扇售。用答案樹來看，也可以對應(yīng)處理當(dāng)前節(jié)點的每一個子節(jié)點嚣艇。 -
for循環(huán)中一般做三件事：1. 處理當(dāng)前節(jié)點承冰；2. 調(diào)用遞歸函數(shù)；3. 撤銷操作（回溯）
void backtracking(arg...) {
if (/* 終止條件 */) {
/* 收集結(jié)果 */
return;
}
for (/* 每一個集合中的元素 */) {
/* 1. 處理當(dāng)前元素 */
/* 2. 調(diào)用遞歸函數(shù) */
/* 3. 撤銷處理（回溯） */
}
return;
}
還要繼續(xù)理解和總結(jié)食零，先多寫一些回溯法的題目困乒。
LeetCode77 組合
- 初見題目的想法：按照以上的回溯模板進行思考
- 首先回溯法的遞歸函數(shù)不返回值
- 遞歸函數(shù)命名為
backtracking - 在分析問題的過程中確定參數(shù)列表
- 先寫遞歸的終止條件：當(dāng)前組合
cur的元素個數(shù)cur.size()等于k，則收集當(dāng)前組合cur贰谣，然后直接返回娜搂。（這步確定需要傳入的參數(shù)為結(jié)果集res，當(dāng)前組合cur吱抚，元素個數(shù)k） - 再寫單層搜索的邏輯：用
for循環(huán)向cur中嘗試加入元素（這步確定需要傳入的參數(shù)為n涌攻，還有防止組合重復(fù)所需的元素的起始值j。
- 按照回溯法的模板進行思考频伤，可以很容易的寫出如下代碼恳谎。我將當(dāng)前組合命名為
cur，和遍歷二叉樹時對節(jié)點的命名類似，提醒自己用樹的形式去理解回溯法因痛。cur對應(yīng)的就是答案的構(gòu)造樹上的某個節(jié)點婚苹。
初見題目的題解代碼如下
class Solution {
public:
void backtracking(vector<vector<int>>& res, int& n, int& k, vector<int> cur, int j) {
if (cur.size() == k) {
res.push_back(cur);
return;
}
for (int i = j; i <= n; i++) {
cur.push_back(i);
backtracking(res, n, k, cur, i + 1);
cur.pop_back();
}
return;
}
vector<vector<int>> combine(int n, int k) {
vector<vector<int>> res;
vector<int> cur;
backtracking(res, n, k, cur, 1);
return res;
}
};
以上代碼的遞歸函數(shù)的參數(shù)列表里的cur沒有傳引用（vector<int> cur），多次拷貝vector鸵膏，代碼效率較差膊升。
改為傳引用vector<int>& cur，可見能顯著提升效率谭企。
class Solution {
public:
void backtracking(vector<vector<int>>& res, int& n, int& k, vector<int> cur, int j) {
if (cur.size() == k) {
res.push_back(cur);
return;
}
for (int i = j; i <= n; i++) {
cur.push_back(i);
backtracking(res, n, k, cur, i + 1);
cur.pop_back();
}
return;
}
vector<vector<int>> combine(int n, int k) {
vector<vector<int>> res;
vector<int> cur;
backtracking(res, n, k, cur, 1);
return res;
}
};
-
組合問題較簡單廓译，在這里在復(fù)習(xí)一次回溯法的三步思考來總結(jié)今天的復(fù)習(xí)：
- 在分析問題的過程中確定遞歸函數(shù)需要的參數(shù)
- 確定遞歸的終止條件，在終止條件里收集結(jié)果
- 確定單層遞歸的處理邏輯
剪枝待第二天復(fù)習(xí)债查。
