代码随想录2.17

回溯

每一道回溯法的题目都可以抽象为树形结构。
回溯的步骤：
①确定回溯函数的参数
②确定终止条件
③确定单层逻辑

回溯算法能解决如下问题：

组合问题：N个数里面按一定规则找出k个数的集合
排列问题：N个数按一定规则全排列，有几种排列方式
切割问题：一个字符串按一定规则有几种切割方式
子集问题：一个N个数的集合里有多少符合条件的子集
棋盘问题：N皇后，解数独等等

回溯模板：

void backtracking(参数) {if (终止条件) {存放结果;return;}for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {处理节点;backtracking(路径，选择列表); // 递归回溯，撤销处理结果}
}

17. 电话号码的字母组合

class Solution {
public:
const string letterMap[10] = {"", // 0"", // 1"abc", // 2"def", // 3"ghi", // 4"jkl", // 5"mno", // 6"pqrs", // 7"tuv", // 8"wxyz", // 9};string s;vector<string> result;void backtracking(string digits, int index) {//index是树的深度if (index == digits.size()) {result.push_back(s);return;}int digit=digits[index]-'0';//因为digits是字符串所以-'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) {if(digits.size()==0){return result;}backtracking(digits,0);return result;}
};

39. 组合总和

class Solution {
public:vector<vector<int>> result;vector<int> path;void backtracking(vector<int>& candidates, int target, int sum,int startindex){ //一般回溯不需要返回值if(sum>target){return;}if(sum==target){result.push_back(path);return;}for(int i = startindex;i<candidates.size();i++){sum+=candidates[i];path.push_back(candidates[i]);backtracking(candidates,target,sum,i);sum-=candidates[i];path.pop_back();}}vector<vector<int>> combinationSum(vector<int>& candidates, int target) {backtracking(candidates,target,0,0);return result;}
};

131. 分割回文串

切割问题其实也是组合问题

class Solution {
public:vector<string> path;vector<vector<string>> result;void backtracking(string s, int startIndex){if(startIndex>=s.size()){result.push_back(path);return;}for(int i=startIndex;i<s.size();i++){if(isHuiwen(s,startIndex,i)){//如果是回文string str = s.substr(startIndex,i-startIndex+1);path.push_back(str);}else{continue;}backtracking(s,i+1);path.pop_back();}}bool isHuiwen(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) {backtracking(s,0);return result;}
};

78. 子集

51. N皇后