电子商务物流网站建设,南昌房信网官网,做装修广告网站好,为什么网站需要静态化生成html今天是个好日子#xff0c;二月二龙抬头#xff0c;龙年龙日龙抬头#xff0c;顺风顺水好兆头#xff0c;万事万物开好头#xff0c;金银珠宝往家里走#xff01;offer往家走#xff01;
回溯算法
回溯法可以解决的问题
组合问题#xff1a;N个数里面按照一定规则找…今天是个好日子二月二龙抬头龙年龙日龙抬头顺风顺水好兆头万事万物开好头金银珠宝往家里走offer往家走
回溯算法
回溯法可以解决的问题
组合问题N个数里面按照一定规则找出k个数的集合切割问题一个字符串按一定规则有几种切割方式子集问题一个N个数的集合里有多少符合条件的子集排列问题N个数按一定规则全排列有几种排列方式棋盘问题N皇后解数独
回溯三部曲
回溯函数模板返回值以及参数回溯函数终止条件回溯搜索的遍历过程
void backtracking(参数){if(终止条件){存放结果;return;}for (选择本层集合中元素(树中节点孩子的数量就是集合的大小)){backtracking(路径选择列表); // 递归回溯撤销处理结果}}组合 for循环横向遍历递归纵向遍历回溯不断调整结果集。 题目
给定两个整数 n 和 k返回范围 [1, n] 中所有可能的 k 个数的组合。
你可以按 任何顺序 返回答案。
77. 组合 - 力扣LeetCode
题解
class Solution {
public:// 创建一个全局变量来放pathvectorint path;// 创建一个全局变量来放所有的pathvectorvectorint result;void backtracking(int n, int k, int startIndex){if(path.size() k){result.push_back(path);return;}for(int i startIndex; i n; i){// 处理节点path.push_back(i);backtracking(n, k, i 1);// 回撤撤销处理节点path.pop_back();}}vectorvectorint combine(int n, int k) {backtracking(n, k, 1);return result;}
};可以剪枝的地方在递归中每一层的for循环所选择的位置比如说for循环选择的起始位置之后的元素个数已不足k个那么就没有必要再进行for循环
组合总和III
题目
找出所有相加之和为 n 的 k 个数的组合且满足下列条件
只使用数字1到9每个数字 最多使用一次
返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次组合可以以任何顺序返回。
216. 组合总和 III - 力扣LeetCode
题解
class Solution {
public:vectorint path;vectorvectorint result;void backtracking(int n, int k, int startIndex){if(path.size() k){ if (accumulate(path.begin(), path.end(), 0) n) result.push_back(path);else return;}for(int i startIndex; i 9; i){path.push_back(i);backtracking(n, k, i 1);path.pop_back();}}vectorvectorint combinationSum3(int k, int n) {backtracking(n, k, 1);return result;}
};电话号码的字母组合
题目
给定一个仅包含数字 2-9 的字符串返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下与电话按键相同。注意 1 不对应任何字母。
17. 电话号码的字母组合 - 力扣LeetCode
题解
index是记录遍历第几个数字了就是用来遍历digits的题目中给出数字字符串同时index也表示树的深度。
class Solution {
public:vectorstring result;string path;void backtracking(const string digits, int index){if(index digits.size()){result.push_back(path);return;}int digit digits[index] - 0;string letters letterMap[digit];for(int i 0; i letters.size(); i){path.push_back(letters[i]);backtracking(digits, index 1);path.pop_back();}}vectorstring letterCombinations(string digits) {if(digits.size() 0) return result;backtracking(digits, 0);return result;}
private:const string letterMap[10] {, //0, //1abc, //2def, //3ghi, //4jkl, //5mno, //6pqrs, //7tuv, //8wxyz, // 9};
};
