驻马店网站建设,网站介绍页面,室内设计网站平面案例,长沙可以做网站的公司1.回溯算法理论基础
回溯法也可以叫做回溯搜索法#xff0c;它是一种搜索的方式。回溯是递归的副产品#xff0c;只要有递归就会有回溯。回溯的本质是穷举,穷举所有可能#xff0c;然后选出我们想要的答案
回溯法解决的问题
组合问题#xff1a;N个数里面按一定规则找出…1.回溯算法理论基础
回溯法也可以叫做回溯搜索法它是一种搜索的方式。回溯是递归的副产品只要有递归就会有回溯。回溯的本质是穷举,穷举所有可能然后选出我们想要的答案
回溯法解决的问题
组合问题N个数里面按一定规则找出k个数的集合切割问题一个字符串按一定规则有几种切割方式子集问题一个N个数的集合里有多少符合条件的子集排列问题N个数按一定规则全排列有几种排列方式棋盘问题N皇后解数独等等
组合是不强调元素顺序的排列是强调元素顺序,组合无序排列有序
回溯法解决的问题都可以抽象为树形结构回溯法解决的都是在集合中递归查找子集集合的大小就构成了树的宽度递归的深度都构成的树的深度。递归就要有终止条件所以必然是一棵高度有限的树N叉树。
回溯三部曲回溯函数模板返回值以及参数回溯算法中函数返回值一般为void需要什么参数就填什么参数。回溯函数终止条件树中就可以看出一般来说搜到叶子节点了也就找到了满足条件的一条答案把这个答案存放起来并结束本层递归。回溯搜索的遍历过程回溯法一般是在集合中递归搜索集合的大小构成了树的宽度递归的深度构成的树的深度。
for循环可以理解是横向遍历backtracking递归就是纵向遍历这样就把这棵树全遍历完了一般来说搜索叶子节点就是找的其中一个结果了
void backtracking(参数) {if (终止条件) {存放结果;return;}for (选择本层集合中元素树中节点孩子的数量就是集合的大小) {处理节点;backtracking(路径选择列表); // 递归回溯撤销处理结果}
}2.组合77题
题目描述
给定两个整数 n 和 k返回 1 ... n 中所有可能的 k 个数的组合。
示例: 输入: n 4, k 2 输出: [ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4], ]
回溯法每次从集合中选取元素可选择的范围随着选择的进行而收缩调整可选择的范围。相当于只需要把达到叶子节点的结果收集起来就可以求得 n个数中k个数的组合集合。int型变量startIndex这个参数用来记录本层递归的中集合从哪里开始遍历集合就是[1,...,n] 。回溯法的搜索过程就是一个树型结构的遍历过程在如下图中可以看出for循环用来横向遍历递归的过程是纵向遍历。
class Solution {
private:vectorvectorint result;//结果集vectorint path;//符合条件结果//递归回溯函数使用startindexvoid 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,i1);//递归纵向遍历下一层从i1搜索path.pop_back();//回溯撤销处理的节点}}
public:vectorvectorint combine(int n, int k) {result.clear();path.clear();backtracking(n,k,1);//return result;}
};
时间复杂度: O(n * 2^n)空间复杂度: O(n)
回溯法就是解决这种k层for循环嵌套的问题把回溯法的搜索过程抽象为树形结构可以直观的看出搜索的过程用回溯法三部曲逐步分析了函数参数、终止条件和单层搜索的过程。
3.组合优化77题
题目描述和2一样
减枝优化剪枝的地方就在递归中每一层的for循环所选择的起始位置。如果for循环选择的起始位置之后的元素个数 已经不足 我们需要的元素个数了那么就没有必要搜索了
class Solution {
private:vectorvectorint result;//结果集vectorint path;//符合条件结果//递归回溯函数使用startindexvoid backtracking(int n,int k,int startindex){//终止条件数组数组大小到递归if(path.size() k){result.push_back(path);//将路径加入结果集中return;}//控制数的横向遍历注意i的范围i进行了减枝操作for(int i startindex;i n - (k-path.size())1;i){path.push_back(i);//处理节点backtracking(n,k,i1);//递归纵向遍历下一层从i1搜索path.pop_back();//回溯撤销处理的节点}}
public:vectorvectorint combine(int n, int k) {result.clear();path.clear();backtracking(n,k,1);return result;}
};
时间复杂度: O(n * 2^n)空间复杂度: O(n)
减枝操作不好理解所以还是可以根据树来进行模拟更方便。
4.组合总和III216题
题目描述
找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数并且每种组合中不存在重复的数字。
说明
所有数字都是正整数。解集不能包含重复的组合。
示例 1: 输入: k 3, n 7 输出: [[1,2,4]]
示例 2: 输入: k 3, n 9 输出: [[1,2,6], [1,3,5], [2,3,4]]
回溯法我们确定函数的参数
targetSumint目标和也就是题目中的n。kint就是题目中要求k个数的集合。sumint为已经收集的元素的总和也就是path里元素的总和。startIndexint为下一层for循环搜索的起始位置。 处理过程 和 回溯过程是一一对应的处理有加回溯就要有减
class Solution {
private:vectorintpath;//路径vectorvectorintresult;//结果集void backtracking(int targetsum,int k,int sum,int startindex){//终止条件if(path.size() k){if(sum targetsum)result.push_back(path);//如果和和目标和相等加入数组return;}//遍历1-9数字使用startindex来控制每次加入的数字for(int i startindex;i 9;i){path.push_back(i);//路径加入sum i;//计算加进来的和backtracking(targetsum,k,sum,i1);//进行递归sum - i;//回溯path.pop_back();//回溯}}
public:vectorvectorint combinationSum3(int k, int n) {path.clear();result.clear();backtracking(n,k,0,1);//注意参数的传入return result;}
};
减枝操作
class Solution {
private:vectorintpath;//路径vectorvectorintresult;//结果集void backtracking(int targetsum,int k,int sum,int startindex){//终止条件if(sum targetsum){return ;//当前和大于了目标和就直接返回减枝操作}if(path.size() k){if(sum targetsum)result.push_back(path);//如果和和目标和相等加入数组return;}//遍历1-9数字使用startindex来控制每次加入的数字,这里和组合那个减枝操作类似代表着所需元素要求来限制for(int i startindex;i 9 - (k-path.size())1;i){path.push_back(i);//路径加入sum i;//计算加进来的和backtracking(targetsum,k,sum,i1);//进行递归sum - i;//回溯path.pop_back();//回溯}}
public:vectorvectorint combinationSum3(int k, int n) {path.clear();result.clear();backtracking(n,k,0,1);//注意参数的传入return result;}
};
时间复杂度: O(n * 2^n)空间复杂度: O(n)
先写树的回溯然后再考虑减枝问题
5.电话号码的字母组合17题
题目描述
给定一个仅包含数字 2-9 的字符串返回所有它能表示的字母组合。
给出数字到字母的映射如下与电话按键相同。注意 1 不对应任何字母。
输入23输出[ad, ae, af, bd, be, bf, cd, ce, cf].
说明尽管上面的答案是按字典序排列的但是你可以任意选择答案输出的顺序。
使用二维数组来进行映射回溯可以解决n个for循环问题注意我们这里不用startindex是因为我们需要从两个不同的字符串来选择字符之前组合那个是因为在同一个集合这个因为在不同集合
class Solution {
private: const string letterMap[10] {, // 0, // 1abc, // 2def, // 3ghi, // 4jkl, // 5mno, // 6pqrs, // 7tuv, // 8wxyz, // 9};
public:vectorstringresult;//结果string s;//字符串//函数和参数定义void backtracking(const string digits,int index){if(index digits.size()){result.push_back(s);//满足条件加入字符串中return ;}int digit digits[index] - 0;//将index指向的数字转为intstring letter letterMap[digit];//取数字对应的字符集//注意这里取index不是startindex是因为不同集合且下标可以从0开始for(int i 0;i letter.size();i){s.push_back(letter[i]);//加入s中backtracking(digits,index1);//递归s.pop_back();//回溯}}vectorstring letterCombinations(string digits) {s.clear();result.clear();if(digits.size() 0){return result;}backtracking(digits,0);return result;}
};
时间复杂度: O(3^m * 4^n)其中 m 是对应四个字母的数字个数n 是对应三个字母的数字个数空间复杂度: O(3^m * 4^n) 总结
回溯理论:回溯本身就是穷举法来实现只要有递归就会有回溯列举出来所有可能可以解决的问题有排列有顺序组合不强调顺序子集切割棋盘问题可以抽象为树形结构在集合中查找子集集合大小作为树的宽度递归深度是树的深度三部曲和递归三部曲很相似,for循环是横向遍历递归是纵向遍历
组合我们从n中选取k个树的集合注意我们使用startindex来控制集合的横向遍历使用递归i来实现集合的纵向遍历我们需要注意结束的终止条件也就是收集结果的过程注意递归后面就需要处理回溯的过程
组合优化问题其实需要考虑是否在遍历i的时候考虑缩小范围达到效果
组合总和iii的问题解决我们来定义的函数需要传进来的参数目标和现在和还有集合大小每次搜索的位置这里和之前处理相似但是需要注意的是终止条件以及回溯过程的写法减枝操作也可以从两个方面来入手实现集合大小还有数值大小来进行处理
电话号码的字母组合需要写对应的字符号对应注意定义的index就可以实现因为从不同集合取元素和之前startindex不一样
