好用的网站开发软件,单位邮箱一般用什么邮箱,外贸询盘网站,学校网站建设汇报ppt本文解决几个问题#xff1a; 回溯算法是什么#xff1f;解决回溯算法相关的问题有什么技巧#xff1f;回溯算法代码是否有规律可循#xff1f; 一、介绍
1.回溯算法是什么#xff1f;
回溯算法就是个多叉树的遍历问题#xff0c;关键在于在前序和后序时间点做一些操作… 本文解决几个问题 回溯算法是什么解决回溯算法相关的问题有什么技巧回溯算法代码是否有规律可循 一、介绍
1.回溯算法是什么
回溯算法就是个多叉树的遍历问题关键在于在前序和后序时间点做一些操作本质是一种暴力枚举算法它和DFS非常相似区别在于回溯算法关注点在于树的树枝DFS关注点在于树的节点。
2.回溯算法的技巧
站在一棵决策树的节点需要考虑三个问题
1、路径也就是已经做出的选择。
2、选择列表也就是你当前可以做的选择。
3、结束条件也就是到达决策树底层无法再做选择的条件。 3. 回溯算法的框架规律
result []
def backtrack(路径选择列表){if(满足结束条件){result.add(路径)return;}for(选择 : 选择列表){//做选择将该选择从选择列表移除路径.add(选择)backtrack(路径, 选择列表)//撤销选择路径.remove(选择)将该选择再加入选择列表}} 其核心就是 for 循环里面的递归在递归调用之前「做选择」在递归调用之后「撤销选择」其实就是在维护每个节点的路径和选择列表信息
抽象地说解决一个回溯问题实际上就是遍历一棵决策树的过程树的每个叶子节点存放着一个合法答案。你把整棵树遍历一遍把叶子节点上的答案都收集起来就能得到所有的合法答案。
我们定义的 backtrack 函数在这棵树上游走同时要正确维护每个节点的属性每当走到树的底层叶子节点其「路径」就是一个答案。 4. 回溯算法和DFS的关系
回溯法 采用试错的思想它尝试分步的去解决一个问题。在分步解决问题的过程中当它通过尝试发现现有的分步答案不能得到有效的正确的解答的时候它将取消上一步甚至是上几步的计算再通过其它的可能的分步解答再次尝试寻找问题的答案。回溯法通常用最简单的递归方法来实现在反复重复上述的步骤后可能出现两种情况
i找到一个可能存在的正确的答案 ii在尝试了所有可能的分步方法后宣告该问题没有答案。
深度优先搜索 是一种用于遍历或搜索树或图的算法。这个算法会 尽可能深 的搜索树的分支。当结点 v 的所在边都己被探寻过搜索将 回溯 到发现结点 v 的那条边的起始结点。这一过程一直进行到已发现从源结点可达的所有结点为止。如果还存在未被发现的结点则选择其中一个作为源结点并重复以上过程整个进程反复进行直到所有结点都被访问为止。 5. 回溯算法的拓展
由于回溯算法的时间复杂度很高因此在遍历的时候如果能够提前知道这一条分支不能搜索到满意的结果就可以提前结束这一步操作称为 剪枝。剪枝是一种技巧通常需要根据不同问题场景采用不同的剪枝策略需要在做题的过程中不断总结。 二、排列、组合、子集相关问题
无论是排列、组合还是子集问题简单说无非就是让你从序列 nums 中以给定规则取若干元素主要有以下几种变体
形式一、元素无重不可复选
形式二、元素可重不可复选
形式三、元素无重可复选
但无论形式怎么变化其本质就是穷举所有解而这些解呈现树形结构所以合理使用回溯算法框架稍改代码框架即可把这些问题一网打尽。 为什么只要记住这两种树形结构就能解决所有相关问题呢
首先组合问题和子集问题其实是等价的这个后面会讲至于之前说的三种变化形式无非是在这两棵树上剪掉或者增加一些树枝罢了。 无重不可复选
核心通过保证元素之间的相对顺序不变来防止出现重复的子集。
具体方法使用 start 参数控制树枝的生长避免产生重复的子集用 track 记录根节点到每个节点的路径的值同时在前序位置把每个节点的路径值收集起来完成回溯树的遍历就收集了所有子集。
例题1子集
代码
class Solution {
public:vectorvectorint ans;vectorint track;void traceback(vectorint nums, int start){// 每个节点的值都是一个子集ans.emplace_back(track);for(int i start; i nums.size(); i){track.emplace_back(nums[i]);traceback(nums, i1);track.pop_back();}}vectorvectorint subsets(vectorint nums) {traceback(nums, 0);return ans;}
}; 例题2组合
分析
代码
class Solution {
public:vectorvectorint ans;vectorint track;void backtrack(int n, int k, int start){if(track.size() k){ans.emplace_back(track);}for(int i start; i n; i){track.emplace_back(i);backtrack(n, k, i1);track.pop_back();}}vectorvectorint combine(int n, int k) {backtrack(n, k, 1);return ans;}
}; 例题3全排列
分析
选择列表就是遍历整个数组如果没有用过某个数字就选择它然后把used数组对应的值设为true然后进入节点递归调用backtrack()出来后撤销选择方式是对路径弹出元素然后更新used数组。
代码
class Solution {
public:vectorvectorint ans;vectorvectorint permute(vectorint nums) {vectorint track;vectorbool used(nums.size(), false);backtrack(nums, track, used);return ans;}void backtrack(vectorintnums, vectorinttrack, vectorbool used){if(track.size() nums.size()){ans.push_back(track);return;}for(int i 0; i nums.size(); i){if(used[i] true){continue;}track.push_back(nums[i]);used[i] true;backtrack(nums, track, used);track.pop_back();used[i] false;}}
};
但如果题目不让你算全排列而是让你算元素个数为 k 的排列怎么算
也很简单改下 backtrack 函数的 base case仅收集第 k 层的节点值即可 可重不可复选
例题4子集 II
分析
元素可重的通用解决方法排序 used数组连续相同的元素只能按顺序取不能前面的没取取后面的。
代码
class Solution {
public:vectorvectorint ans;vectorint track;void backtrack(vectorint nums, int start, vectorbool used){ans.emplace_back(track);for(int i start; inums.size(); i){// 剪枝逻辑值相同的相邻树枝只遍历第一条if(i0 nums[i] nums[i-1] used[i-1] false){continue;}track.emplace_back(nums[i]);used[i] true;backtrack(nums, i1, used);used[i] false;track.pop_back();}}vectorvectorint subsetsWithDup(vectorint nums) {sort(nums.begin(), nums.end());vectorbool used(nums.size(), false);backtrack(nums, 0, used);return ans;}
}; 例题5组合总和 II
代码
class Solution {
public:vectorint track;vectorvectorint ans;void traceback(vectorint candidates, int target, vectorbool used, int start){int sum accumulate(track.begin(), track.end(), 0);if(sum target){ans.emplace_back(track);return;}if(sum target){return;}for(int i start ; i candidates.size(); i){if(used[i] || ( i0 candidates[i-1] candidates[i] used[i-1] false)){continue;}used[i] true;track.emplace_back(candidates[i]);traceback(candidates, target, used, i1);track.pop_back();used[i] false;}}vectorvectorint combinationSum2(vectorint candidates, int target) {sort(candidates.begin(), candidates.end());vectorbool used(candidates.size(), false);traceback(candidates, target, used, 0);return ans;}
}; 例题6全排列 II
分析
所有相同的数字他的排列组合只有一个记住这一点然后用nums[i-1] nums[i] used[i-1] false这个条件去限制就可以做到相同数字只有一个排列进入答案。
代码
class Solution {
public:vectorvectorint ans;void backtrack(vectorint nums, vectorint track, vectorbool used){if(track.size() nums.size()){ans.push_back(track);return;}for(int i 0; i nums.size(); i){if(used[i]true || (i 0 nums[i-1] nums[i] used[i-1] false)){continue;}used[i] true;track.push_back(nums[i]);backtrack(nums, track, used);track.pop_back();used[i] false;}}vectorvectorint permuteUnique(vectorint nums) {sort(nums.begin(), nums.end());vectorint track;vectorbool used(nums.size(), false);backtrack(nums, track, used);return ans;}
}; 元素无重可复选
例题7组合总和
分析
想解决这种类型的问题也得回到回溯树上我们不妨先思考思考标准的子集/组合问题是如何保证不重复使用元素的
答案在于 backtrack 递归时输入的参数 start这个 i 从 start 开始那么下一层回溯树就是从 start 1 开始从而保证 nums[start] 这个元素不会被重复使用那么反过来如果我想让每个元素被重复使用我只要把 i 1 改成 i 即可
代码
class Solution {
public:vectorvectorint ans;vectorint track;int sum;void backtrack(vectorint nums, int target, int start){sum accumulate(track.begin(), track.end(), 0);if(sum target){return;}if(sum target){ans.emplace_back(track);return;}for(int i start; inums.size(); i){track.emplace_back(nums[i]);backtrack(nums, target, i);track.pop_back();}}vectorvectorint combinationSum(vectorint nums, int target) {backtrack(nums, target, 0);return ans;}
}; 其他
例题8排列序列
代码
思路1回溯 剪枝
class Solution {
public:vectorvectorchar ans;vectorchar track;int cnt 0;void backtrack(int n, vectorbool used){if(track.size() n){ans.emplace_back(track);cnt;return;}for(int i 0; i n; i){if(used[i]){continue;}track.emplace_back(i10);used[i] true;backtrack(n, used);used[i] false;track.pop_back();}}string getPermutation(int n, int k) {vectorbool used(n, false);//如果数字过大直接定位第一位if( k 120){int factorial 1;int first;for(int i 1; i n; i){factorial * i;}first k/factorial;k % factorial;track.emplace_back(first 1 0);used[first] true;}//业务逻辑backtrack(n, used);string ret(ans[k-1].begin(), ans[k-1].end());return ret;}
}; 思路2直接定位
class Solution {
public:string getPermutation(int n, int k) {vectorchar ans, array;int tmp, ncp n, f 1;array.emplace_back(1);for(int i 1; i ncp; i){f* i;array.emplace_back(i10);}f* ncp;k--;while(n ! 0){f / n--;tmp k/f;k % f;ans.emplace_back(array[tmp%ncp]);array.erase(array.begin() tmp);}string ret(ans.begin(), ans.end());return ret;}
}; 例题9复原 IP 地址
代码
class Solution {
public:vectorstring ans;vectorint segment;void backtrack(string s,int pos, int segcnt){int segnum 0;if(pos s.size() segcnt 4){string track;for(int i 0; i 4; i){track to_string(segment[i]);if(i ! 3) track .;}ans.emplace_back(track);//到达末尾return回去return;}else if((segcnt 4 pos ! s.size()) || (pos s.size() segcnt ! 4)){return;}if(s[pos] 0){segment[segcnt] 0;backtrack(s, pos 1, segcnt 1);//撤销选择的方法是returnreturn;}for(int i pos; is.size(); i){segnum segnum*10 (s[i] - 0);if(segnum 0 segnum 0xFF){segment[segcnt] segnum;backtrack(s, i1, segcnt 1);}else{return;}}}vectorstring restoreIpAddresses(string s) {segment.resize(4);backtrack(s, 0, 0);return ans;}
}; 三、Flood FillDFS
例题10单词搜索
分析
本题说是回溯其实很像DFS的方法参考
DFS 算法解决岛屿题目
代码
class Solution {
public:int m, n;bool backtrack(vectorvectorchar board, string word, int pos, int i, int j){if(i m || j n || i0 || j0 || board[i][j] ! word[pos]){return false;}if(pos word.size()-1){return true;}bool res;board[i][j] 0;res backtrack(board, word, pos1, i1, j) || backtrack(board, word, pos1, i-1, j)||backtrack(board, word, pos1, i, j1) || backtrack(board, word, pos1, i, j-1);board[i][j] word[pos];return res;}bool exist(vectorvectorchar board, string word) {m board.size();n board[0].size();for(int i 0; i m; i){for(int j 0; jn; j){if(backtrack(board, word, 0, i, j))return true;}}return false;}
}; 例题11被围绕的区域
DFS 算法解决岛屿题目 中有详解 例题12岛屿数量
DFS 算法解决岛屿题目 中有详解 例题13图像渲染
分析
dfs模板越界返回 访问返回 非目标返回 dfs递归
代码
class Solution {
public:int m, n;int samecolor;void dfs(vectorvectorint image, int i, int j, int color){if(im || j n|| i0 || j0){return;}if(image[i][j] color){return;}if(image[i][j] ! samecolor){return;}image[i][j] color;dfs(image, i1, j, color);dfs(image, i, j1, color);dfs(image, i, j-1, color);dfs(image, i-1, j, color);}vectorvectorint floodFill(vectorvectorint image, int sr, int sc, int color) {m image.size(); n image[0].size();samecolor image[sr][sc];dfs(image, sr, sc, color);return image;}
}; 三、字符串中的回溯问题
例题14电话号码的字母组合
代码
class Solution {
public:vectorstring ans;string track;vectorstringarray;void backtrack(string digits, int pos){if(track.size() digits.size()){ans.emplace_back(track);return;}//根据数字算出其对应的选择有哪些for(char c : array[digits[pos]-0]){track c;backtrack(digits, pos1);track.erase(track.end()-1);}}vectorstring letterCombinations(string digits) {if(digits.size() 0){return ans;}array.resize(10);for(int i 0; i18; i){array[i/32] ia;}array[7] s; array[8] tuv; array[9] wxyz;backtrack(digits, 0);return ans;}
};
改良这里用hashmap存储选择数组比较好
class Solution {
public:vectorstring ans;string track;unordered_mapchar, string array;void backtrack(string digits, int pos){if(track.size() digits.size()){ans.emplace_back(track);return;}for(char c : array[digits[pos]]){track c;backtrack(digits, pos1);track.erase(track.end()-1);}}vectorstring letterCombinations(string digits) {if(digits.size() 0){return ans;}array {{2, abc},{3, def},{4, ghi},{5, jkl},{6, mno},{7, pqrs},{8, tuv},{9, wxyz}};backtrack(digits, 0);return ans;}
}; 例题15字母大小写全排列
代码
class Solution {
public:vectorstring ans;string track;string choice(char c){string ret;ret c;if(c a c z){ret toupper(c);}if(c A c Z){ret tolower(c);}return ret;}void backtrack(string s, int pos){if(track.size() s.size()){ans.emplace_back(track);return;}//做选择for(char c : choice(s[pos])){track c;backtrack(s, pos1);track.erase(track.end()-1);}}vectorstring letterCasePermutation(string s) {backtrack(s, 0);return ans;}
}; 例题16括号生成
分析 代码 三、游戏问题
例题17N 皇后
分析 代码 例题18解数独
分析 代码 例题19祖玛游戏
分析 代码 例题20扫雷游戏
分析 代码 四、总结
i全排列解决方法:
用used数组来选取没有选过的元素
ii元素可重的通用解决方法
排序 used 数组连续相同的元素只能按顺序取不能前面的没取取后面的。
iii组合/子集非排列解决方法
backtrack传start进去控制取元素的顺序避免重复访问。
可重复选递归的时候传 i
不可重复选递归的时候传 i 1
比如[1, 2, 3]固定一的时候[1,3]取走了下一次固定3如果不控制顺序还会取到[3,1]这样按组合的逻辑来说就是重复的。
iii只要从树的角度思考这些问题看似复杂多变实则改改 base case 就能解决
ivvectorchar转化为string直接string str(v.begin(), v.end())
vstring删去最后一个元素 string.erase(string.end()-1);
