1.回溯算法.基礎

1.回溯算法

基礎知識
題目
- 1.組合
- 2.組合-優化
- 3.組合總和|||
- 4.電話號碼和字母組合
- 5.組合總和
- 6.組合總和II
- 7.分割回文串
- 8.復原IP地址

基礎知識

回溯法也可以叫做回溯搜索法，它是一種搜索的方式。回溯是遞歸的副產品，只要有遞歸就會有回溯
因為回溯的本質是窮舉，窮舉所有可能，然后選出我們想要的答案，如果想讓回溯法高效一些，可以加一些剪枝的操作，但也改不了回溯法就是窮舉的本質。

回溯算法能解決的問題：

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

理解回溯法：
回溯法解決的問題都可以抽象為樹形結構，所有回溯法的問題都可以抽象為樹形結構。因為回溯法解決的都是在集合中遞歸查找子集，集合的大小就構成了樹的寬度，遞歸的深度就構成了樹的深度。
遞歸就要有終止條件，所以必然是一棵高度有限的樹（N叉樹）。

回溯法模板

回溯函數模板返回值以及函數，習慣是函數起名字為backtracking，函數返回值一般為void
回溯函數終止條件，一般來說是搜到葉子節點了
回溯搜索的遍歷過程

for循環就是遍歷集合的區間，一個節點有多少個子節點，for循環就會執行多少次。

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

這份模板很重要，后面做回溯法的題目都基本是按照該模板解決。
回溯和遞歸是相輔相成的，回溯法的效率，回溯法其實就是暴力查找，并不是什么高效的算法。最后我們講到回溯法解決的問題都可以抽象為樹形結構（N叉樹），。并給出了回溯法的模板。

題目

1.組合

（題目鏈接）
給定兩個整數 n 和 k，返回 1 … n 中所有可能的 k 個數的組合。
這題是回溯法的經典題目，直接解法是通過k個for循環，不考慮順序的情況下完成組合問題。但當k值較大時，暴力搜索的代碼太過冗長。因此可以使用遞歸法，每次遞歸中嵌套一個for循環，那么遞歸就可以用于解決過曾的嵌套系統問題。例如：
在這里插入圖片描述

    std::vector<std::vector<int>> res;std::vector<int> path;void backtracking(int n, int k, int startindex){if(path.size()==k){res.push_back(path);return;}for(int i=startindex; i<=n; i++){path.push_back(i);backtracking(n, k, i+1);path.pop_back();}}vector<vector<int>> combine(int n, int k) {res.clear();path.clear();backtracking(n,k,1);return res;}

2.組合-優化

題目1中的回溯法是可以剪枝優化的，可以剪枝的地方就在遞歸中每一層的for循環所選擇的起始位置，以此避免一些沒有必要的循環。在組合問題中如果for循環選擇的起始位置之后的元素個數已經不足我們需要的元素個數了，那么就沒有必要搜索了。
1.已經選擇的元素個數：path.size()；2.所需需要的元素個數為: k - path.size()；3.列表中剩余元素（n-i） >= 所需需要的元素個數（k - path.size()）；4.在集合n中至多要從該起始位置 : i <= n - (k - path.size()) + 1，這里+1是因為for循環取的索引值是左閉區間。
修改之后的for循環條件如下

for (int i = startIndex; i <= n - (k - path.size()) + 1; i++) // i為本次搜索的起始位置

3.組合總和|||

（題目鏈接）
找出所有相加之和為 n 的 k 個數的組合。組合中只允許含有 1 - 9 的正整數，并且每種組合中不存在重復的數字。說明：所有數字都是正整數；解集不能包含重復的組合。
這題相當于在組合問題的基礎上多了一個限制，就是找到和為n的k個數的組合，而整個集合已經是固定的1~9。

    std::vector<std::vector<int>> res;std::vector<int> path;void backtracking(int tarSum, int k, int sum, int startindex){if(path.size()==k && sum == tarSum){res.push_back(path);}for(int i=startindex; i<=9 - (k - path.size()) + 1; i++){sum += i;path.push_back(i);if(sum > tarSum){sum -= i;path.pop_back();return;}backtracking(tarSum, k, sum, i+1);sum -= i;path.pop_back();}}    vector<vector<int>> combinationSum3(int k, int n) {res.clear();path.clear();backtracking(n, k, 0, 1);return res;}

4.電話號碼和字母組合

（題目鏈接）
給定一個僅包含數字 2-9 的字符串，返回所有它能表示的字母組合
在這里插入圖片描述
例如：輸入：“23”；輸出：[“ad”, “ae”, “af”, “bd”, “be”, “bf”, “cd”, “ce”, “cf”]。（盡管上面的答案是按字典序排列的，但是你可以任意選擇答案輸出的順序。）
根據輸入的數字，可以分為一層遞歸，所以本題是要解決如下三個問題：

數字和字母的映射
輸入數字還包含異常的情況，例如1*#的情況

解決第一個問題，需要建立一個0~9隊形string charMap[10]的字符串數組結構；
確定回溯函數參數：需要字符串收集葉子節點的結果，然后用一個字符串數組res保存，這兩個變量設置為全局。除此之外，局部變量為接收題目中給的string digits，以及int index-記錄digits第幾個數字。
返回條件，當index==digits.size()。

    const string letterMap[10] = {"", // 0"", // 1"abc", // 2"def", // 3"ghi", // 4"jkl", // 5"mno", // 6"pqrs", // 7"tuv", // 8"wxyz", // 9};std::vector<std::string> res;std::string s;void backtracking(const string& digits, int index){if(index==digits.size()){res.push_back(s);return;}int digit = digits[index]-'0';string letters = letterMap[digit];for(int i=0; i<letters.size(); i++){s.push_back(letters[i]);backtracking(digits, index+1);s.pop_back();}}vector<string> letterCombinations(string digits) {res.clear();s.clear();if(digits.size()==0) return res;backtracking(digits, 0);return res;}

此時不需要在backtracking中設置startindex，因為是多個集合取組合，各個集合之間相互不影響，那么就不用startIndex。但如果是一個集合來求組合的話，就需要startIndex。
時間復雜度: O(3^ m*4^ n , 空間復雜度: O(3^ m * 4^n)，其中 m 是對應三個字母的數字個數，n 是對應四個字母的數字個數。

5.組合總和

（題目鏈接）
給定一個無重復元素的數組 candidates 和一個目標數 target ，找出 candidates 中所有可以使數字和為 target 的組合。說明：candidates 中的數字可以無限制重復被選取；所有數字（包括 target）都是正整數；解集不能包含重復的組合。例如輸入：candidates = [2,3,5], target = 8；所求解集為： [ [2,2,2,2], [2,3,3], [3,5] ]。
與之前組合問題不同的是，這題沒有數量的限制，可以無限重復，但總和有限制，所以遞歸的次數也是有限制的。
遞歸函數參數：兩個全局變量，二維數組result存放結果集，數組path存放符合條件的結果；題目傳入的集合candidates, 和目標值target。使用int sum來統計path里的總和，同時需要startindex來控制for循環的起始位置
終止條件：當sum大于等于tarsum時，遞歸終止。
當然這題也是可以作剪枝優化處理的，就是在for循環條件-如果下一層的sum（就是本層的 sum + candidates[i]）已經大于target，就可以結束本輪for循環的遍歷

    std::vector<std::vector<int>> res;std::vector<int> path;void backtracking(std::vector<int>& candidates, int target, int sum, int startindex){if(sum==target){res.push_back(path);return;}for(int i=startindex; i<candidates.size() && sum+candidates[i]<=target; i++){sum += candidates[i];path.push_back(candidates[i]);// 此處傳入i，而不是i+1，是因為元素可以重復backtracking(candidates, target, sum, i);sum -= candidates[i];path.pop_back();}}vector<vector<int>> combinationSum(vector<int>& candidates, int target) {res.clear();path.clear();std::sort(candidates.begin(), candidates.end());// 排序有利于加速剪枝backtracking(candidates, target, 0, 0);return res;}

6.組合總和II

（題目鏈接）
給定一個數組 candidates 和一個目標數 target ，找出 candidates 中所有可以使數字和為 target 的組合。說明：candidates 中的每個數字在每個組合中只能使用一次，所有數字（包括目標數）都是正整數。解集不能包含重復的組合
這題與第4題的區別是，candidates中的數字只能用一次，而且該數組可能存在重復的元素。正確理解重復的組合：“使用過”在組合問題（樹形結構）上有兩個維度：同一個樹枝上使用，同一個數層上使用。結合題目我們要去重的是同一樹層上”使用過“的元素，同一樹枝上都是一個組合里的元素，不用去重。
在這里插入圖片描述
因此需要還需要加一個bool型數組used，用來記錄同一樹枝上的元素是否使用過。

    std::vector<std::vector<int>> res;std::vector<int> path;void backtracking(std::vector<int>& candidates, int target, int sum, int startindex, std::vector<bool> used){if(sum==target){res.push_back(path);return;}for(int i=startindex; i<candidates.size() && sum+candidates[i]<=target;i++ ){// 這一步的基礎是sort，因此相等的元素會排列在一起if(i>0 && candidates[i]== candidates[i-1] && used[i-1]==false) continue;sum += candidates[i];path.push_back(candidates[i]);used[i] = true;backtracking(candidates, target, sum, i+1, used);sum -= candidates[i];path.pop_back();used[i] = false;}}vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {std::vector<bool> used(candidates.size(), false);res.clear();path.clear();std::sort(candidates.begin(), candidates.end());backtracking(candidates, target, 0, 0, used);return res;}

7.分割回文串

（題目鏈接）
給定一個字符串 s，將 s 分割成一些子串，使每個子串都是回文串。返回 s 所有可能的分割方案。例如示例: 輸入: “aab” 輸出: [ [“aa”,“b”], [“a”,“a”,“b”] ]

切割問題其實類似組合問題：切割問題最后可以抽象為一顆樹的結構

組合問題：選取一個a之后，在bcdef中再去選取第二個，選取b之后在cdef中再選取第三個…。
切割問題：切割一個a之后，在bcdef中再去切割第二段，切割b之后在cdef中再切割第三段…。

遞歸函數參數：全局變量數組path存放切割后回文的子串，二維數組result存放結果集。參數還需要startIndex，因為切割過的地方，不能重復切割。遞歸參數需要傳入startIndex，表示下一輪遞歸遍歷的起始位置，這個startIndex就是切割線。另外切割的是以startindex的左閉區間，因此當startindex0時會出現空切==的情況出現。
終止條件：切割線切到了字符串最后面，說明找到了一種切割方法。
如何判斷回文字符串：使用雙指針法，左端，右端向中間靠攏，令char[i]==char[j]就是回文字符串。

    std::vector<std::vector<std::string>> res;std::vector<std::string> path;void backtracking(std::string& s, int startindex){if(startindex>=s.size()){res.push_back(path);return;}for(int i=startindex; i<s.size() ; i++){if(ispalindrome(s, startindex, i)){std::string str = s.substr(startindex, i-startindex+1);path.push_back(str);                }else continue;backtracking(s, i+1);path.pop_back();}}bool ispalindrome(const std::string& s, int start, int end){for(int i=start, j=end; i<j; i++, j--){if(s[i]!=s[j]) return false;}return true;}vector<vector<string>> partition(string s) {res.clear();path.clear();backtracking(s, 0);return res;}

8.復原IP地址

（題目鏈接）
給定一個只包含數字的字符串，復原它并返回所有可能的 IP 地址格式。有效的 IP 地址正好由四個整數（每個整數位于 0 到 255 之間組成，且不能含有前導 0），整數之間用 ‘.’ 分隔。
遞歸參數：這題類似分割回文串，因為需要添加逗號，需要設置變量pointNum記錄；
遞歸終止條件：當pointNum==3時，驗證一下第四段是否合法，如果合法就加入集合里；
單層搜索的邏輯：在循環遍歷里截取子串，不過需要判斷該子串是否合法，如果合法，則添加.表示已經分割；如果不合法就結束本層循環。
判斷子串是否合法：段位以0為開頭的數字不合法；段位里有非整數字符；段位大于255

    std::vector<std::string> res;void backtracking(std::string& s, int startindex, int pointnum){if(pointnum==3){if(isvalid(s, startindex, s.size()-1)) res.push_back(s);return;}for(int i=startindex; i<s.size(); i++){if(isvalid(s, startindex, i)){s.insert(s.begin()+i+1, '.');pointnum++;backtracking(s, i+2, pointnum);pointnum--; // 回溯s.erase(s.begin()+i+1);}else break; // 首段不合法，直接結束本層該分支的循環}}bool isvalid(const string& s, int start, int end){// 異常if(start>end) return false;// 開頭為0if(s[start]=='0' && start!=end) return false;int num=0;for(int i=start; i<=end; i++){// 不在0~9范圍內的字符if(s[i]>'9' || s[i]<'0') return false;num = num*10 + (s[i]-'0');// 超出255范圍的字符if(num>255) return false;}return true;}vector<string> restoreIpAddresses(string s) {res.clear();if(s.size()<4 || s.size()>12) return res;backtracking(s, 0, 0);return res;}