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

—day22

---

前言

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

---

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

文章講解

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

回溯法解決的問(wèn)題

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

回溯法模板

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

---

一、77. 組合

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

思路：

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

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

---

二、216. 組合總和 III

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

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

思路：

1. 遞歸函數(shù)參數(shù)以及返回值：參數(shù)：n，k，startIndex（每一層遞歸需要避開(kāi)已經(jīng)遍歷過(guò)的數(shù)，所以需要一個(gè)索引去記錄遍歷到[1,n]的那個(gè)數(shù)字了）
2. 終止條件：path大小滿足k的時(shí)候終止，判斷總和是否為n，是則加入結(jié)果集。
3. 單層處理邏輯：for循環(huán)遍歷[1,9]，添加單個(gè)數(shù)字到path中，再遞歸添加下一個(gè)數(shù)字（startIndex+1）。
4. 剪枝：跟77. 組合 一樣，for循環(huán)中只需要到i < n - (k - 目前存的個(gè)數(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; //剪枝，超過(guò)目標(biāo)總和了直接返回if (path.size() == k) { //組合大小滿足的就要返回，沒(méi)必要繼續(xù)下去了if (sum == n) result.push_back(path); //組合大小滿足，總和也滿足才加入結(jié)果集return;}//遍歷[1,n]依次尋找結(jié)果集, 遍歷到剩余元素個(gè)數(shù)不足以滿足k的時(shí)候就可以停了，題目要求只使用數(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的組合，并且傳入遍歷的起始下標(biāo)和目前的總和path.pop_back();sum -= i;}return;}vector<vector<int>> combinationSum3(int k, int n) {backtracking(k, n, 0, 1);return result;}
};

---

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

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

思路：
需要有一個(gè)數(shù)組來(lái)存下每個(gè)數(shù)字對(duì)應(yīng)的字母，用一個(gè)string[]，用下標(biāo)對(duì)應(yīng)數(shù)字，string對(duì)應(yīng)字符串。

遞歸思路：

1. 遞歸函數(shù)參數(shù)以及返回值：參數(shù)：digits，Index（這個(gè)索引是告訴遞歸函數(shù)遍歷到了digits的那個(gè)數(shù)字）
2. 終止條件：當(dāng)遍歷完digits時(shí)終止，將目前存的string放入結(jié)果集。
3. 單層處理邏輯：for循環(huán)遍歷digits[Index]對(duì)應(yīng)的字符串，添加單個(gè)字母到string中，再遞歸添加下一個(gè)數(shù)字對(duì)應(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; //單個(gè)結(jié)果void backtracking (string &digits, int index) {if (index == digits.size()) { //當(dāng)遍歷完digits字母時(shí)終止并保存結(jié)果result.push_back(s);return;}int digit = digits[index] - '0'; //將index指向的數(shù)字轉(zhuǎn)為intstring 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因?yàn)橄乱粚邮翘幚韉igits的下一個(gè)字母了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í)了回溯算法的理論和其中解決組合類(lèi)的題目。

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

明天繼續(xù)加油！