网站游戏网站开发设计菲律宾,广告电商,广州30万人感染,望都网站建设文章目录 回溯算法理论什么是回溯法回溯法的效率回溯法解决的问题理解回溯法回溯法模板 组合问题I描述题解优化 组合总和III描述题解 电话号码的字母组合描述题解 组合总和描述题解 组合总和II描述题解 分割回文串描述题解 复原IP地址描述题解 子集描述题解 子集II描述题解 递增… 文章目录 回溯算法理论什么是回溯法回溯法的效率回溯法解决的问题理解回溯法回溯法模板 组合问题I描述题解优化 组合总和III描述题解 电话号码的字母组合描述题解 组合总和描述题解 组合总和II描述题解 分割回文串描述题解 复原IP地址描述题解 子集描述题解 子集II描述题解 递增子序列描述题解 全排列描述题解 全排列 II描述题解 重新安排行程 难描述如何处理死循环映射关系的记录 题解 N皇后 难描述题解 解数独 跳过描述题解 回溯算法理论
什么是回溯法
回溯法也可以叫做回溯搜索法它是一种搜索的方式。
回溯是递归的副产品只要有递归就会有回溯。
回溯法的效率
纯暴力搜索
虽然回溯法很难很不好理解但是回溯法并不是什么高效的算法。 因为回溯的本质是穷举穷举所有可能然后选出我们想要的答案如果想让回溯法高效一些可以加一些剪枝的操作但也改不了回溯法就是穷举的本质。
回溯法解决的问题
组合问题N个数里面按一定规则找出k个数的集合切割问题一个字符串按一定规则有几种切割方式子集问题一个N个数的集合里有多少符合条件的子集排列问题N个数按一定规则全排列有几种排列方式棋盘问题N皇后解数独等等
理解回溯法
回溯法解决的问题都可以抽象为树形结构
因为回溯法解决的都是在集合中递归查找子集集合的大小就构成了树的宽度递归的深度都构成的树的深度。
递归就要有终止条件所以必然是一棵高度有限的树N叉树。
回溯法模板
伪代码
void backtracking(参数) {if (终止条件) {存放结果;return;}for (选择本层集合中元素树中节点孩子的数量就是集合的大小) {处理节点;backtracking(路径选择列表); // 递归回溯撤销处理结果}
}组合问题I
题目链接
描述
给定两个整数 n 和 k返回 1 … n 中所有可能的 k 个数的组合。
示例: 输入: n 4, k 2 输出: [ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4], ]
题解
class Solution {
private:vectorvectorintres;//最后的结果vectorintpath;//放单个组合void backtracking(int n,int k,int startIndex){if (path.size()k){res.push_back(path);return;}for (int i startIndex; i n; i) {path.push_back(i);backtracking(n,k,i1);//使用递归代表for 一层递归一个for循环path.pop_back();}}
public:// 给定两个整数 n 和 k返回范围 [1, n] 中所有可能的 k 个数的组合vectorvectorint combine(int n, int k) {backtracking(n,k,1);return res;}
};优化
如果nk4 那么第一层for循环从i2之后都毫无意义
可以剪枝的地方就在递归中每一层的for循环所选择的起始位置。
如果for循环选择的起始位置之后的元素个数 已经不足 我们需要的元素个数了那么就没有必要搜索了。
优化过程
已经存入的元素的个数path.size()还需要的元素的个数k-path.size()表中剩余元素的个数n-i 所需元素k - path.size()在集合n中至多要从该起始位置 : i n - (k - path.size()) 1开始遍历 为什么有个1呢因为包括起始位置我们要是一个左闭的集合。
举个例子n 4k 3 目前已经选取的元素为0path.size为0n - (k - 0) 1 即 4 - ( 3 - 0) 1 2。 从2开始搜索都是合理的可以是组合[2, 3, 4]。
class Solution {
private:vectorvectorintres;//最后的结果vectorintpath;//放单个组合void backtracking(int n,int k,int startIndex){if (path.size()k){res.push_back(path);return;}for (int i startIndex; i n-(k-path.size())1; i) {//优化后的for循环path.push_back(i);backtracking(n,k,i1);//使用递归代表for 一层递归一个for循环path.pop_back();}}
public:// 给定两个整数 n 和 k返回范围 [1, n] 中所有可能的 k 个数的组合vectorvectorint combine(int n, int k) {backtracking(n,k,1);return res;}
};组合总和III
题目链接
描述
找出所有相加之和为 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]]
题解
class Solution {
private:vectorvectorint res;vectorint path;/**** param k 1-9之间选取的个数* param n k个数的和为n* param startIndex 循环开始的数* param sum 目前已经和为多少*/void backtracking(int k, int n, int startIndex, int sum) {if (sum n)return;if (path.size() k) {if (sum n)res.push_back(path);return; // 如果path.size() k 但sum ! targetSum 直接返回}for (int i startIndex; i 9 - (k - path.size()) 1; i) {// 剪枝path.push_back(i);sum i;backtracking(k, n, i 1, sum);path.pop_back();sum - i;}}public:vectorvectorint combinationSum3(int k, int n) {path.clear();res.clear();backtracking(k, n, 1, 0);return res;}
};电话号码的字母组合
题目链接
描述
给定一个仅包含数字 2-9 的字符串返回所有它能表示的字母组合。
给出数字到字母的映射如下与电话按键相同。注意 1 不对应任何字母。 输入“23” 输出[“ad”, “ae”, “af”, “bd”, “be”, “bf”, “cd”, “ce”, “cf”]. 说明尽管上面的答案是按字典序排列的但是你可以任意选择答案输出的顺序。
题解
class Solution {
private:vectorstring res;string path;vectorstringflags{abc,def,ghi,jkl,mno,pqrs,tuv,wxyz};void backtracking(string digits,int len,int startIndex) {if (path.size()len){res.push_back(path);return;}string letterflags[digits[startIndex]-0-2];for (int i 0; i letter.size(); i) {path.push_back(letter[i]);backtracking(digits,len,startIndex1);path.pop_back();}}public:vectorstring letterCombinations(string digits) {int len digits.size();if (!len)return res;backtracking(digits,len,0);return res;}
};组合总和
题目链接
描述
给定一个无重复元素的数组 candidates 和一个目标数 target 找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的数字可以无限制重复被选取。
说明
所有数字包括 target都是正整数。 解集不能包含重复的组合。 示例 1
输入candidates [2,3,6,7], target 7, 所求解集为 [ [7], [2,2,3] ] 示例 2
输入candidates [2,3,5], target 8, 所求解集为 [ [2,2,2,2], [2,3,3], [3,5] ]
题解
class Solution {
private:vectorvectorint res;vectorint path;void backtracking(vectorint canidates, int target, int nowSum, int startIndex) {if (nowSum target)return;if (nowSum target) {res.push_back(path);return;}int len canidates.size();for (int i startIndex; i len; i) {path.push_back(canidates[i]);nowSum canidates[i];backtracking(canidates, target, nowSum, i);path.pop_back();nowSum - canidates[i];}}public:vectorvectorint combinationSum(vectorint candidates, int target) {backtracking(candidates, target, 0, 0);return res;}
};组合总和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] ] 示例 2: 输入: candidates [2,5,2,1,2], target 5, 所求解集为: [ [1,2,2], [5] ]
题解
class Solution {
private:vectorvectorintres;vectorintpath;void backtracking(vectorintcandidates,int target,int nowSum,int index){if (nowSumtarget)return;if (nowSumtarget){res.push_back(path);return;}for (int i index; i candidates.size(); i) {if (iindexcandidates[i]candidates[i-1])continue;path.push_back(candidates[i]);nowSumcandidates[i];backtracking(candidates,target,nowSum,i1);path.pop_back();nowSum-candidates[i];}}
public:vectorvectorint combinationSum2(vectorint candidates, int target) {sort(candidates.begin(),candidates.end());backtracking(candidates,target,0,0);return res;}
};分割回文串
题目链接
描述
给定一个字符串 s将 s 分割成一些子串使每个子串都是回文串。
返回 s 所有可能的分割方案。
示例: 输入: “aab” 输出: [ [“aa”,“b”], [“a”,“a”,“b”] ]
题解
class Solution {
private:vectorvectorstringres;vectorstringpath;bool isPalindrome(const strings,int start,int end){for (int i start,jend; i j; i,--j) {if (s[i]!s[j])return false;}return true;}void backtracking(const strings,int startIndex){// 如果起始位置已经大于s的大小说明已经找到了一组分割方案了if (startIndexs.size()){res.push_back(path);return;}for (int i startIndex; i s.size(); i) {if (isPalindrome(s,startIndex,i)){// 获取[startIndex,i]在s中的子串string strs.substr(startIndex,i-startIndex1);path.push_back(str);}else//如果不是回文串 那么跳过continue;backtracking(s,i1);path.pop_back();}}
public:vectorvectorstring partition(string s) {backtracking(s,0);return res;}
};复原IP地址
题目链接
描述
给定一个只包含数字的字符串复原它并返回所有可能的 IP 地址格式。
有效的 IP 地址 正好由四个整数每个整数位于 0 到 255 之间组成且不能含有前导 0整数之间用 ‘.’ 分隔。
例如“0.1.2.201” 和 “192.168.1.1” 是 有效的 IP 地址但是 “0.011.255.245”、“192.168.1.312” 和 “192.1681.1” 是 无效的 IP 地址。
示例 1
输入s “25525511135” 输出[“255.255.11.135”,“255.255.111.35”] 示例 2
输入s “0000” 输出[“0.0.0.0”] 示例 3
输入s “1111” 输出[“1.1.1.1”]
题解
class Solution {
private:vectorstring res;// startIndex: 搜索的起始位置pointNum:添加逗点的数量void backtracking(string s, int startIndex, int pointNum) {if (pointNum 3) {//逗号个数为3时 分割结束//判断第四段字符串是否合法if (vaildIP(s, startIndex, s.size() - 1)) {res.push_back(s);return;}}for (int i startIndex; i s.size(); i) {if (vaildIP(s, startIndex, i)) {// 判断 [startIndex,i] 这个区间的子串是否合法s.insert(s.begin() i 1, .);//在i后面插入逗号pointNum;backtracking(s, i 2, pointNum);--pointNum;s.erase(s.begin() i 1);} else break;//不合法直接结束本层循环 因为如果这一段不合法那么再加一个字符也是不合法的}}bool vaildIP(const string s, int start, int end) {if (start end)return false;if (s[start] 0 start ! end)return false;int num0;for (int i start; i end; i) {if (s[i]0||s[i]9)return false;numnum*10s[i]-0;if (num255)return false;}return true;}public:vectorstring restoreIpAddresses(string s) {backtracking(s, 0, 0);return res;}
};子集
题目链接
描述
给定一组不含重复元素的整数数组 nums返回该数组所有可能的子集幂集。
说明解集不能包含重复的子集。
示例: 输入: nums [1,2,3] 输出: [ [3], [1], [2], [1,2,3], [1,3], [2,3], [1,2], [] ]
题解
class Solution {
private:vectorvectorintres;vectorintsubSet;void backtracking(vectorintnums,int startIndex){res.push_back(subSet); // 收集子集要放在终止添加的上面否则会漏掉自己if (startIndexnums.size())return;//终止条件 可以不加因为下面的循环当startIndexsize的时候就不会进行了for (int i startIndex; i nums.size(); i) {subSet.push_back(nums[i]);backtracking(nums,i1);subSet.pop_back();}}
public:vectorvectorint subsets(vectorint nums) {backtracking(nums,0);return res;}
};子集II
题目链接
描述
给定一个可能包含重复元素的整数数组 nums返回该数组所有可能的子集幂集。
说明解集不能包含重复的子集。
示例:
输入: [1,2,2] 输出: [ [2], [1], [1,2,2], [2,2], [1,2], [] ]
题解
和子集I思路差不多不过多了一个去重操作
class Solution {
private:vectorvectorintres;vectorintpath;void backtracking(vectorintnums,int startIndex){res.push_back(path);if (startIndexnums.size())return;for (int i startIndex; i nums.size(); i) {if (istartIndexnums[i]nums[i-1])continue;path.push_back(nums[i]);backtracking(nums,i1);path.pop_back();}}
public:vectorvectorint subsetsWithDup(vectorint nums) {sort(nums.begin(),nums.end());backtracking(nums,0);return res;}
};递增子序列
题目链接
描述
给定一个整型数组, 你的任务是找到所有该数组的递增子序列递增子序列的长度至少是2。
示例:
输入: [4, 6, 7, 7] 输出: [[4, 6], [4, 7], [4, 6, 7], [4, 6, 7, 7], [6, 7], [6, 7, 7], [7,7], [4,7,7]] 说明:
给定数组的长度不会超过15。 数组中的整数范围是 [-100,100]。 给定数组中可能包含重复数字相等的数字应该被视为递增的一种情况。
题解
有更好的优化 比如unordered_set换成数组 因为题目给出了数字的范围
class Solution {
private:vectorvectorint res;vectorint path;void backtracking(vectorint nums, int startIndex) {if (path.size() 2) {res.push_back(path);//后面不可以加return 因为要遍历全部}unordered_setint uset;//uset仅负责一层 也就是一层递归调用函数for (int i startIndex; i nums.size(); i) {if (!path.empty() nums[i] path.back() || uset.find(nums[i]) ! uset.end())continue;uset.insert(nums[i]);//记录本层本元素已经使用 不影响下一层 下一次递归path.push_back(nums[i]);backtracking(nums, i 1);path.pop_back();}}public:vectorvectorint findSubsequences(vectorint nums) {backtracking(nums, 0);return res;}
};全排列
题目链接
描述
给定一个 没有重复 数字的序列返回其所有可能的全排列。
示例:
输入: [1,2,3] 输出: [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ]
题解
排列问题
每层都是从0开始搜索而不是startIndex需要used数组记录path里都放了哪些元素了
class Solution {
private:vectorvectorint res;vectorint path;void backtracking(vectorint nums,vectorboolused) {if (path.size() nums.size()) {// 此时说明找到了一组res.push_back(path);return;}for (int i 0; i nums.size(); i) {if (used[i])continue;// path里已经收录的元素直接跳过used[i]true;path.push_back(nums[i]);backtracking(nums,used);used[i]false;path.pop_back();}}public:vectorvectorint permute(vectorint nums) {vectorboolused(nums.size(),false);backtracking(nums,used);return res;}
};全排列 II
题目链接
描述
给定一个可包含重复数字的序列 nums 按任意顺序 返回所有不重复的全排列。
示例 1
输入nums [1,1,2] 输出 [[1,1,2], [1,2,1], [2,1,1]] 示例 2
输入nums [1,2,3] 输出[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]] 提示
1 nums.length 8 -10 nums[i] 10
题解
借用代码随想录网站的图
树层上去重(used[i - 1] false)的树形结构如下 树枝上去重used[i - 1] true的树型结构如下
class Solution {
private:vectorvectorint res;vectorint path;void backtracking(vectorint nums, vectorbool used) {if (path.size() nums.size()) {res.push_back(path);return;}for (int i 0; i nums.size(); i) {// used[i - 1] true说明同一树枝nums[i - 1]使用过// used[i - 1] false说明同一树层nums[i - 1]使用过// 如果同一树层nums[i - 1]使用过则直接跳过if (i 0 nums[i] nums[i - 1] used[i - 1] false)continue;if (!used[i]) {used[i] true;path.push_back(nums[i]);backtracking(nums, used);path.pop_back();used[i] false;}}}public:vectorvectorint permuteUnique(vectorint nums) {vectorbool used(nums.size(), false);sort(nums.begin(), nums.end());backtracking(nums, used);return res;}
};重新安排行程 难
题目链接
描述
给定一个机票的字符串二维数组 [from, to]子数组中的两个成员分别表示飞机出发和降落的机场地点对该行程进行重新规划排序。所有这些机票都属于一个从 JFK肯尼迪国际机场出发的先生所以该行程必须从 JFK 开始。
提示
如果存在多种有效的行程请你按字符自然排序返回最小的行程组合。例如行程 [“JFK”, “LGA”] 与 [“JFK”, “LGB”] 相比就更小排序更靠前 所有的机场都用三个大写字母表示机场代码。 假定所有机票至少存在一种合理的行程。 所有的机票必须都用一次 且 只能用一次。 示例 1
输入[[“MUC”, “LHR”], [“JFK”, “MUC”], [“SFO”, “SJC”], [“LHR”, “SFO”]] 输出[“JFK”, “MUC”, “LHR”, “SFO”, “SJC”] 示例 2
输入[[“JFK”,“SFO”],[“JFK”,“ATL”],[“SFO”,“ATL”],[“ATL”,“JFK”],[“ATL”,“SFO”]] 输出[“JFK”,“ATL”,“JFK”,“SFO”,“ATL”,“SFO”] 解释另一种有效的行程是 [“JFK”,“SFO”,“ATL”,“JFK”,“ATL”,“SFO”]。但是它自然排序更大更靠后。
本题中存在的几个难点
如何处理死循环 出发机场和到达机场也会重复的如果在解题的过程中没有对集合元素处理好就会死循环
映射关系的记录
题目要求如果有多个路径字母序靠前排在前面
一个机场映射多个机场多个机场之间要按照字母序排序
可以使用unordered_mapstring,mapstring,int targets 也就是对应
map/set 自动排序按照数字、字母序从小到大排序
unordered_map出发机场map到达机场航班次数
在遍历 unordered_map出发机场, map到达机场, 航班次数 targets的过程中可以使用航班次数这个字段的数字做相应的增减来标记到达机场是否使用过了
如果“航班次数”大于零说明目的地还可以飞如果“航班次数”等于零说明目的地不能飞了而不用对集合做删除元素或者增加元素的操作。
题解
class Solution {
private:unordered_mapstring, mapstring, int targets;vectorstring result;// 对于本题目而言 我们不需要遍历跟到节点的所有可能只需要找到一个行程就是在树形结构中唯一的一条通向叶子节点的路线// 所以需要返回值bool backtracking(vectorvectorstring tickets, int ticketNum) {if (ticketNum 1 result.size())return true;for (pairconst string, int target: targets[result[result.size() - 1]]) {if (target.second) {result.push_back(target.first);target.second--;if (backtracking(tickets, ticketNum))return true;target.second;result.pop_back();}}return false;}public:vectorstring findItinerary(vectorvectorstring tickets) {for (const vectorstring ticket: tickets)targets[ticket[0]][ticket[1]];result.push_back(JFK);backtracking(tickets, tickets.size());return result;}
};N皇后 难
题目链接
描述
n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上并且使皇后彼此之间不能相互攻击。
给你一个整数 n 返回所有不同的 n 皇后问题 的解决方案。
不能同行 不能同列 不能同斜线
每一种解法包含一个不同的 n 皇后问题 的棋子放置方案该方案中 ‘Q’ 和 ‘.’ 分别代表了皇后和空位。
题解
class Solution {
private:vectorvectorstringres;bool isValid(int row,int col,int n,vectorstringpath){//检查列for(int i 0; i row; i)if(path[i][col]Q)return false;/* 检查行是多余的因为在单层搜索的过程中每一层递归只会选for循环也就是同一行里的一个元素所以不用去重了。for(int i 0;i col;i)if(path[row][i]Q)return false; *///45度for(int i col-1,jrow-1;i 0j0;--i,--j){if(path[j][i]Q)return false;}//135度for(int i row-1,jcol1;i0jn ;--i,j){if(path[i][j]Q)return false;}return true;}void backtracking(int n,int start,vectorstringpath){if(startn){res.push_back(path);return;}for(int i 0 ;i n ;i){if(isValid(start,i,n,path)){path[start][i]Q;backtracking(n,start1,path);path[start][i].;}}}
public:vectorvectorstring solveNQueens(int n) {vectorstringpath(n,string(n,.));backtracking(n,0,path);return res;}
};
解数独 跳过
题目链接
描述
编写一个程序通过填充空格来解决数独问题。
一个数独的解法需遵循如下规则 数字 1-9 在每一行只能出现一次。 数字 1-9 在每一列只能出现一次。 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。 空白格用 ‘.’ 表示。 提示
给定的数独序列只包含数字 1-9 和字符 ‘.’ 。 你可以假设给定的数独只有唯一解。 给定数独永远是 9x9 形式的。
题解
