代碼隨想錄算法訓(xùn)練營

—day22

---

前言

今天是算法營的第22天，希望自己能夠堅持下來！
今日任務(wù)：
● 回溯算法理論基礎(chǔ)
● 77. 組合
● 216.組合總和III
● 17.電話號碼的字母組合

---

回溯算法理論基礎(chǔ)

文章講解

• 回溯法也可以叫做回溯搜索法，它是一種搜索的方式。
• 回溯是遞歸的副產(chǎn)品，只要有遞歸就會有回溯。
• 回溯的本質(zhì)是窮舉，是一種純暴力的方法，嵌套多個for循環(huán) 回溯法解決的問題都可以抽象為樹形結(jié)構(gòu)
• 回溯的遞歸函數(shù)一般叫backtracking，返回值一般為void，參數(shù)比較多，沒那么容易確定下來，所以一般是先寫邏輯，然后需要什么參數(shù)，就填什么參數(shù)。

回溯法解決的問題

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

回溯法模板

void backtracking(參數(shù)) {if (終止條件) {存放結(jié)果;return;}for (選擇：本層集合中元素（樹中節(jié)點孩子的數(shù)量就是集合的大小）) {處理節(jié)點;backtracking(路徑，選擇列表); // 遞歸回溯，撤銷處理結(jié)果}
}

---

一、77. 組合

題目鏈接
文章講解
視頻講解

思路：

1. 遞歸函數(shù)的參數(shù)和返回值：參數(shù)：n，k，startIndex（每一層遞歸需要避開已經(jīng)遍歷過的數(shù)，所以需要一個索引去記錄遍歷到[1,n]的那個數(shù)字了）
2. 終止條件：存下來的path大小已經(jīng)滿足k了
3. 單層遞歸的邏輯：for循環(huán)遍歷[1,n]，添加單個數(shù)字到path中，再遞歸添加下一個數(shù)字（startIndex+1）。
4. 剪枝：其實單層遍歷的時候不需要遍歷滿[1,n]，當遍歷到剩下的數(shù)字個數(shù)已經(jīng)不足以組成k個的時候已經(jīng)不需要再遍歷了，所以在for循環(huán)中，使用i < n - (k - 目前存的個數(shù)) + 1，這里+1是因為范圍包含了startIndex

class Solution {
public:vector<int> path;vector<vector<int>> result;void backtracking(int n, int k, int startIndex) {//當組合大小滿足k時放入結(jié)果集if (path.size() == k) {result.push_back(path);return;}//遍歷[1,n]依次尋找結(jié)果集, 遍歷到剩余元素個數(shù)不足以滿足k的時候就可以停了for (int i = startIndex; i <= n - (k - path.size()) + 1;  i ++) {path.push_back(i); //放入ibacktracking(n, k, i + 1); //尋找跟i能滿足k的組合，并且傳入遍歷的起始下標path.pop_back(); //取出i}return;}vector<vector<int>> combine(int n, int k) {backtracking(n, k, 1);return result;}
};

---

二、216. 組合總和 III

題目鏈接
文章講解
視頻講解

跟77. 組合 其實就是多了個和的約束，思路是差不多的。并且要注意題目說只用數(shù)字1到9。

思路：

1. 遞歸函數(shù)參數(shù)以及返回值：參數(shù)：n，k，startIndex（每一層遞歸需要避開已經(jīng)遍歷過的數(shù)，所以需要一個索引去記錄遍歷到[1,n]的那個數(shù)字了）
2. 終止條件：path大小滿足k的時候終止，判斷總和是否為n，是則加入結(jié)果集。
3. 單層處理邏輯：for循環(huán)遍歷[1,9]，添加單個數(shù)字到path中，再遞歸添加下一個數(shù)字（startIndex+1）。
4. 剪枝：跟77. 組合 一樣，for循環(huán)中只需要到i < n - (k - 目前存的個數(shù)) + 1，并且總和大于n了也可以直接返回，不需要再遍歷了。

代碼如下：

class Solution {
public:vector<int> path;vector<vector<int>> result;void backtracking (int k, int n, int sum, int startIndex) {if (sum > n) return; //剪枝，超過目標總和了直接返回if (path.size() == k) { //組合大小滿足的就要返回，沒必要繼續(xù)下去了if (sum == n) result.push_back(path); //組合大小滿足，總和也滿足才加入結(jié)果集return;}//遍歷[1,n]依次尋找結(jié)果集, 遍歷到剩余元素個數(shù)不足以滿足k的時候就可以停了，題目要求只使用數(shù)字19for (int i = startIndex; i <= 9 - (k - path.size()) + 1; i ++) {sum += i;path.push_back(i);backtracking(k, n, sum, i + 1);//尋找跟i能滿足k的組合，并且傳入遍歷的起始下標和目前的總和path.pop_back();sum -= i;}return;}vector<vector<int>> combinationSum3(int k, int n) {backtracking(k, n, 0, 1);return result;}
};

---

三、17. 電話號碼的字母組合

題目鏈接
文章講解
視頻講解

思路：
需要有一個數(shù)組來存下每個數(shù)字對應(yīng)的字母，用一個string[]，用下標對應(yīng)數(shù)字，string對應(yīng)字符串。

遞歸思路：

1. 遞歸函數(shù)參數(shù)以及返回值：參數(shù)：digits，Index（這個索引是告訴遞歸函數(shù)遍歷到了digits的那個數(shù)字）
2. 終止條件：當遍歷完digits時終止，將目前存的string放入結(jié)果集。
3. 單層處理邏輯：for循環(huán)遍歷digits[Index]對應(yīng)的字符串，添加單個字母到string中，再遞歸添加下一個數(shù)字對應(yīng)的字母（index+1）。

class Solution {
private:const string letterMap[10] = {"", //0"", //1"abc",//2"def",//3"ghi",//4"jkl",//5"mno",//6"pqrs",//7"tuv",//8"wxyz"//9};public:vector<string> result; //結(jié)果集string s; //單個結(jié)果void backtracking (string &digits, int index) {if (index == digits.size()) { //當遍歷完digits字母時終止并保存結(jié)果result.push_back(s);return;}int digit = digits[index] - '0'; //將index指向的數(shù)字轉(zhuǎn)為intstring letters = letterMap[digit]; //取出數(shù)字對應(yīng)的字母集for (int i = 0; i < letters.size(); i++) { //遍歷子母集獲取字母組合s.push_back(letters[i]);backtracking(digits, index + 1); //遞歸，index+1因為下一層是處理digits的下一個字母了s.pop_back(); //回溯}}vector<string> letterCombinations(string digits) {s.clear();result.clear();if (digits.size() == 0) return result;backtracking(digits, 0);return result;}
};

---

總結(jié)

今天主要學(xué)習(xí)了回溯算法的理論和其中解決組合類的題目。

• 回溯算法是一種純暴力的方法，嵌套多個for循環(huán)
• 回溯法解決的問題都可以抽象為樹形結(jié)構(gòu)
• 組合類的題目需要使用一個索引去告訴函數(shù)遍歷到哪里了

明天繼續(xù)加油！