营销策划与运营团队,做网站优化找谁,网站跳出率计算,建站精灵网站模板回溯算法 理论基础回溯法的效率回溯法解决的问题回溯法模板 组合思路回溯法三部曲 代码 组合#xff08;优化#xff09;组合总和III思路代码 电话号码的字母组合思路回溯法来解决n个for循环的问题回溯三部曲代码 组合总和思路代码 组合总和II思路代码 理论基础
什么是回溯法… 回溯算法 理论基础回溯法的效率回溯法解决的问题回溯法模板 组合思路回溯法三部曲 代码 组合优化组合总和III思路代码 电话号码的字母组合思路回溯法来解决n个for循环的问题回溯三部曲代码 组合总和思路代码 组合总和II思路代码 理论基础
什么是回溯法 回溯法也可以叫做回溯搜索法它是一种搜索的方式。
在二叉树系列中我们已经不止一次提到了回溯例如二叉树以为使用了递归其实还隐藏着回溯。 回溯是递归的副产品只要有递归就会有回溯。
所以以下讲解中回溯函数也就是递归函数指的都是一个函数。
回溯法的效率
回溯法的性能如何呢这里要和大家说清楚了虽然回溯法很难很不好理解但是回溯法并不是什么高效的算法。 因为回溯的本质是穷举穷举所有可能然后选出我们想要的答案如果想让回溯法高效一些可以加一些剪枝的操作但也改不了回溯法就是穷举的本质。
那么既然回溯法并不高效为什么还要用它呢 因为没得选一些问题能暴力搜出来就不错了撑死了再剪枝一下还没有更高效的解法。
那么都什么问题这么牛逼只能暴力搜索。
回溯法解决的问题
回溯法一般可以解决如下几种问题
组合问题N个数里面按一定规则找出k个数的集合 切割问题一个字符串按一定规则有几种切割方式 子集问题一个N个数的集合里有多少符合条件的子集 排列问题N个数按一定规则全排列有几种排列方式 棋盘问题N皇后解数独等等
回溯法模板
卡哥总结的回溯算法模板。
回溯三部曲
1.回溯函数模板返回值以及参数回溯算法中函数返回值一般为void。再来看一下参数因为回溯算法需要的参数可不像二叉树递归的时候那么容易一次性确定下来所以一般是先写逻辑然后需要什么参数就填什么参数。
回溯函数伪代码如下
void backtracking(参数)2.回溯函数终止条件 什么时候达到了终止条件树中就可以看出一般来说搜到叶子节点了也就找到了满足条件的一条答案把这个答案存放起来并结束本层递归。
所以回溯函数终止条件伪代码如下
if (终止条件) {存放结果;return;
}3.回溯搜索的遍历过程 在上面我们提到了回溯法一般是在集合中递归搜索集合的大小构成了树的宽度递归的深度构成的树的深度。
回溯函数遍历过程伪代码如下
for (选择本层集合中元素树中节点孩子的数量就是集合的大小) {处理节点;backtracking(路径选择列表); // 递归回溯撤销处理结果
}for循环可以理解是横向遍历backtracking递归就是纵向遍历这样就把这棵树全遍历完了一般来说搜索叶子节点就是找的其中一个结果了。
组合
力扣题目链接
给定两个整数 n 和 k返回 1 … n 中所有可能的 k 个数的组合。
示例: 输入: n 4, k 2 输出: [ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4], ]
思路 可以看出这棵树一开始集合是 1234 从左向右取数取过的数不再重复取。
第一次取1集合变为234 因为k为2我们只需要再取一个数就可以了分别取234得到集合[1,2] [1,3] [1,4]以此类推。
每次从集合中选取元素可选择的范围随着选择的进行而收缩调整可选择的范围。
图中可以发现n相当于树的宽度k相当于树的深度。
那么如何在这个树上遍历然后收集到我们要的结果集呢
图中每次搜索到了叶子节点我们就找到了一个结果。
相当于只需要把达到叶子节点的结果收集起来就可以求得 n个数中k个数的组合集合。
回溯法三部曲
递归函数的返回值以及参数 在这里要定义两个全局变量一个用来存放符合条件单一结果一个用来存放符合条件结果的集合。
vectorvectorint result; // 存放符合条件结果的集合
vectorint path; // 用来存放符合条件结果函数里一定有两个参数既然是集合n里面取k个数那么n和k是两个int型的参数。
然后还需要一个参数为int型变量startIndex这个参数用来记录本层递归中集合从哪里开始遍历集合就是[1,…,n] 。
为什么要有这个startIndex呢 startIndex 就是防止出现重复的组合。 从下图中红线部分可以看出在集合[1,2,3,4]取1之后下一层递归就要在[2,3,4]中取数了那么下一层递归如何知道从[2,3,4]中取数呢靠的就是startIndex。 所以需要startIndex来记录下一层递归搜索的起始位置。
那么整体代码如下
vectorvectorint result; // 存放符合条件结果的集合
vectorint path; // 用来存放符合条件单一结果
void backtracking(int n, int k, int startIndex)回溯函数终止条件 什么时候到达所谓的叶子节点了呢
path这个数组的大小如果达到k说明我们找到了一个子集大小为k的组合了在图中path存的就是根节点到叶子节点的路径。 此时用result二维数组把path保存起来并终止本层递归。
所以终止条件代码如下
if (path.size() k) {result.push_back(path);return;
}单层搜索的过程 回溯法的搜索过程就是一个树型结构的遍历过程在如下图中可以看出for循环用来横向遍历递归的过程是纵向遍历。 如此我们才遍历完图中的这棵树。 for循环每次从startIndex开始遍历然后用path保存取到的节点i。 可以看出backtracking递归函数通过不断调用自己一直往深处遍历总会遇到叶子节点遇到了叶子节点就要返回。 backtracking的下面部分就是回溯的操作了撤销本次处理的结果。
代码如下
for (int i startIndex; i n; i) { // 控制树的横向遍历path.push_back(i); // 处理节点backtracking(n, k, i 1); // 递归控制树的纵向遍历注意下一层搜索要从i1开始path.pop_back(); // 回溯撤销处理的节点
}代码
class Solution {
public:vectorint paths;vectorvectorintresult;void backtracking(int n , int k ,int startidx){if(paths.size()k){result.push_back(paths);return;} for(int i startidx;i n ;i){paths.push_back(i);backtracking(n,k,i1);paths.pop_back();}}vectorvectorint combine(int n, int k) {backtracking(n,k,1);return result;}
};组合优化
组合总和III
力扣题目链接
找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数并且每种组合中不存在重复的数字。
说明 所有数字都是正整数。 解集不能包含重复的组合。
示例 1: 输入: k 3, n 7 输出: [[1,2,4]]
思路
代码
class Solution {
public:vectorvectorintresult;vectorintpaths;int sum 0;void backtracking(int n , int k,int startidx){if(paths.size()k) return;if(sum n) return;if(paths.size()k sumn ){result.push_back(paths);return ;}for(int i startidx; i9;i){paths.push_back(i);sumi;backtracking(n,k,i1);paths.pop_back();sum-i;}}vectorvectorint combinationSum3(int k, int n) {backtracking(n,k,1);return result;}
};电话号码的字母组合
力扣题目链接
给定一个仅包含数字 2-9 的字符串返回所有它能表示的字母组合。
给出数字到字母的映射如下与电话按键相同。注意 1 不对应任何字母。 示例 输入digits “23” 输出[“ad”,“ae”,“af”,“bd”,“be”,“bf”,“cd”,“ce”,“cf”]
思路
数字和字母如何映射 可以使用map或者定义一个二维数组例如string letterMap[10]来做映射我这里定义一个二维数组代码如下
const string letterMap[10] {, // 0, // 1abc, // 2def, // 3ghi, // 4jkl, // 5mno, // 6pqrs, // 7tuv, // 8wxyz, // 9
};回溯法来解决n个for循环的问题
例如输入“23”抽象为树形结构如图所示 图中可以看出遍历的深度就是输入23的长度而叶子节点就是我们要收集的结果输出[“ad”, “ae”, “af”, “bd”, “be”, “bf”, “cd”, “ce”, “cf”]。
回溯三部曲
确定回溯函数参数
首先需要一个字符串s来收集叶子节点的结果然后用一个字符串数组result保存起来这两个变量我依然定义为全局。 再来看参数参数指定是有题目中给的string digits然后还要有一个参数就是int型的index。 这个index是记录遍历第几个数字了就是用来遍历digits的题目中给出数字字符串同时index也表示树的深度。
代码如下
vectorstring result;
string s;
void backtracking(const string digits, int index)确定终止条件 例如输入用例23两个数字那么根节点往下递归两层就可以了叶子节点就是要收集的结果集。
那么终止条件就是如果index 等于 输入的数字个数digits.size了本来index就是用来遍历digits的。
然后收集结果结束本层递归。
代码如下
if (index digits.size()) {result.push_back(s);return;
}这里index跳出循环后的大小就是数组的大小
确定单层遍历逻辑
首先要取index指向的数字并找到对应的字符集手机键盘的字符集。
然后for循环来处理这个字符集代码如下
int digit digits[index] - 0; // 将index指向的数字转为int
string letters letterMap[digit]; // 取数字对应的字符集
for (int i 0; i letters.size(); i) {s.push_back(letters[i]); // 处理backtracking(digits, index 1); // 递归注意index1一下层要处理下一个数字了s.pop_back(); // 回溯
}注意这里for循环可不像是在回溯算法求组合问题和回溯算法求组合总和中从startIndex开始遍历的。
因为本题每一个数字代表的是不同集合也就是求不同集合之间的组合而上述两道题都是求同一个集合中的组合
代码
class Solution {
public:const vectorstringphones {,,abc,def,ghi,jkl,mno,pqrs,tuv,wxyz};vectorstringresult;string path;void backtracking(string digits , int index){if( index digits.size()){result.push_back(path);return;}int num digits[index] - 0;string words phones[num];for(int i 0 ; i words.size();i){path.push_back(words[i]);backtracking(digits,index1);path.pop_back();}}vectorstring letterCombinations(string digits) {if(digits.size()0)return result;backtracking(digits,0);return result;}
};组合总和
力扣题目链接
给定一个无重复元素的数组 candidates 和一个目标数 target 找出 candidates 中所有可以使数字和为 target 的组合。 candidates 中的数字可以无限制重复被选取。
说明 所有数字包括 target都是正整数。 解集不能包含重复的组合。 示例 1
输入candidates [2,3,6,7], target 7, 所求解集为 [ [7], [2,2,3] ]
思路
代码
class Solution {
public:vectorvectorintresult;vectorintpaths;void backtracking(vectorint candidates , int target ,int sum , int startidx){if(sum target){return;}if(sum target){result.push_back(paths);return ;}for(int i startidx ; i candidates.size();i){paths.push_back(candidates[i]);sum candidates[i];backtracking(candidates,target,sum,i);sum - candidates[i];paths.pop_back();}}vectorvectorint combinationSum(vectorint candidates, int target) {backtracking(candidates,target,0,0);return result;}
};组合总和II
力扣题目链接
给定一个数组 candidates 和一个目标数 target 找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用一次。
说明 所有数字包括目标数都是正整数。解集不能包含重复的组合。
示例 1: 输入: candidates [10,1,2,7,6,1,5], target 8, 所求解集为:
[[1, 7],[1, 2, 5],[2, 6],[1, 1, 6]
]思路
如果 candidates 中有重复元素可能会生成重复的组合。为了避免这种情况首先需要对 candidates 进行排序。排序后相同的数字会排列在一起从而可以更容易地跳过重复的组合。
不排序去重
代码
class Solution {
public:vectorvectorintresult;vectorintpath;void backtracking(vectorint candidates, int target, int sum,int startidx ){if(sum target)return;if(sumtarget){result.push_back(path);return;}for(int i startidx;icandidates.size();i){if(istartidx candidates[i]candidates[i-1])continue;path.push_back(candidates[i]);sum candidates[i];backtracking(candidates,target,sum,i1);sum - candidates[i];path.pop_back();}}vectorvectorint combinationSum2(vectorint candidates, int target) {sort(candidates.begin(),candidates.end());backtracking(candidates,target,0,0);return result;}
};
