网站是用什么编程语言编写的,酒店网站制作策划,wordpress改造熊掌号,继续网站建设前言
本篇博客将分两步来进行#xff0c;首先谈谈我对回溯法的理解#xff0c;然后通过若干道题来进行讲解#xff0c;最后总结
对回溯法的理解
回溯法可以看做蛮力法的升级版#xff0c;它在解决问题时的每一步都尝试所有可能的选项#xff0c;最终找出所以可行的方案…前言
本篇博客将分两步来进行首先谈谈我对回溯法的理解然后通过若干道题来进行讲解最后总结
对回溯法的理解
回溯法可以看做蛮力法的升级版它在解决问题时的每一步都尝试所有可能的选项最终找出所以可行的方案。回溯法非常适合解决由多个步骤组成的问题并且每个步骤都有多个选项在每一步选择了其中一个选项之后就进入下一步然后又会面临新的选项就这样重复选择直至最终的状态。
用回溯法解决问题的过程可以形象地用一个树形结构表示求解问题的每个步骤可以看作树中的一个节点。如果在某一步有n个可能的选项每个选项是树中的一条边经过这些边就可以到达该节点的个子节点。
在采用回溯法解决问题时如果到达树形结构的叶节点就找到了问题的一个解。如果希望找到更多的解那么还可以回溯到它的父节点再次尝试父节点其它的选项。如果父节点所有可能的选项都已经试过那么再回溯到父节点的父节点以尝试它的其他选项这样逐层回溯到树的根节点。因此采用回溯法解决问题的过程实质上是在树形结构中从根节点开始进行深度优先遍历。通常回溯法的深度优先遍历用递归代码实现。
由于回溯法是在所有选项形成的树上进行深度优先遍历如果解决问题的步骤比较多或每个步骤都面临多个选项那么遍历整棵树将需要较多的时间如果明确知道某些子树没有必要遍历那么在遍历的时候应该避开这些子树以优化效率。通常将使用回溯法时避免遍历不必要的子树的方法称为剪枝。
用回溯解决集合的组合排列问题
组合不看重元素顺序因此两个集合中元素个数相同各元素个数相同这两个集合就是一个组合。
排列看重元素顺序因此两个集合中元素个数相同各元素个数相同但是元素顺序不同的话这两个集合就是两个不同的排列。
所有子集
题目 分析
以集合【1,2】为例有两个元素每个元素都面临选和不选两种选择树形图如下图所示 本题中生成一个子集可分为若干步并且每一步都面临若干选择这正是采用回溯法的典型场景。
代码
class Solution {
public:vectorvectorint vv;vectorint v;vectorint cnums;vectorvectorint subsets(vectorint nums) {cnumsnums;dfs(0);return vv;}void dfs(int pos){if(poscnums.size()){vv.push_back(v);return;}dfs(pos1);v.push_back(cnums[pos]);dfs(pos1);v.pop_back();}
};
在回溯到父节点时清除之前相应的修改即恢复现场。
包含K个元素的组合
题目 分析
集合的一个组合也是一个子集因此求集合的组合的过程和求子集的过程是一样的这个题目较钱一道题只是增加了一个限制条件即只找出包含K个数字的组合只需要在前一道题的基础上稍加修改即可就可以找出所有包含K个数字的组合。
代码
class Solution {
public:vectorvectorint vv;vectorint v;vectorvectorint combine(int n, int k) {dfs(n,k,1);return vv;}void dfs(int n,int k,int pos){if(v.size()k){vv.push_back(v);return;}if(posn){dfs(n,k,pos1);v.push_back(pos);dfs(n,k,pos1);v.pop_back();}}
};
允许重复选择元素的组合
题目 分析
这个题目仍然是关于组合的但组合中的一个数字可以出现任意次可以以不变应万变用回溯法来解决这个问题。
能够用回溯法解决的问题都能够分成若干步来解决每一步都面临若干选择。对于从集合中选取数字组成组合的问题而言集合中有多少个数字解决这个问题就需要多少步每一步都从集合中取出一个下标为i的数字此时面临两个选择。一个选择是跳过这个数字不将该数字添加到组合中那么这一步实际上什么都不做接下来处理下标为i1的数字。另一个选择是将该数字添加到组合中由于一个数字可以重复在集合中出现也就是说下一步可能再次选择同一个数字因此下一步仍然处理下标为i的数字。
代码
class Solution {
public:vectorvectorint vv;vectorint v;vectorvectorint combinationSum(vectorint candidates, int target) {helper(candidates,target,0);return vv;}void helper(vectorint candidates, int target,int pos){if(target0){vv.push_back(v);return;}else if(poscandidates.size() target0){helper(candidates,target,pos1);v.push_back(candidates[pos]);helper(candidates,target-candidates[pos],pos);v.pop_back();}}
};
应用回溯法解决问题时如果有可能应尽可能剪枝以优化时间效率。由于题目明确指出数组中的所有数字都是正整数因此当组合中已有数字之和已经大于目标值时即递归函数helper的参数target的值小于0时就没必要再考虑数组中还没有处理的数字因为再在组合中添加任意正整数元素之后和会更大一定找不到新的符合条件的组合也就没必要再继续尝试这就是函数helper中else if的条件中补充了一个target大于0的判断条件的原因。
包含重复元素集合的组合
题目 分析
这个题目和之前几个题目与组合相关的题目相比最大的不同之处在于输入的集合中有重复的数字但输出不得包含重复的组合如果输入的集合中有重复的数字不经过特殊处理将产生重复的集合。
避免重复的组合的方法就是当在某一步决定跳过某个值为m的数字时跳过所有值为m的数字。
为了方便跳过后面所有值相同的数字可以将集合中的数字排序将相同的数字放在一起这样方便比较数字。当决定跳过某个值的数字时可以按顺序扫描后面的数字直到找到不同的只为止。
代码
class Solution {
public:vectorvectorint vv;vectorint v;vectorvectorint combinationSum2(vectorint candidates, int target) {sort(candidates.begin(),candidates.end());helper(candidates,target,0);return vv;}void helper(vectorint candidates, int target,int pos){if(target0){vv.push_back(v);return;}else if(poscandidates.size() target0){int nextpos;while(nextcandidates.size() candidates[next]candidates[pos]) next;helper(candidates,target,next);v.push_back(candidates[pos]);helper(candidates,target-candidates[pos],pos1);v.pop_back();}}
};
没有重复元素集合的全排列
题目 分析
假设集合有n个元素那么生成一个全排列需要n步当生成排列的第一个数字时会面临n个选项即n个数字都有可能成为排列的第1个数字生成排列的第二个数字会面临n-1个选项即剩下的n-1个数字都有可能成为排列的第2个数字以此类推。看起来解决这个问题可以分为n步每一步都面临若干选项这就是典型的适用回溯法的场景。
方法一
使用一个bool类型数组来标记是否被访问过每次填写排列的第I个位置时都从前往后一次遍历没有被访问过的数字加入排列。
class Solution {
public:vectorvectorint vv;vectorint v;vectorint cpnums;bool vis[10];vectorvectorint permute(vectorint nums) {cpnumsnums;helper(0);return vv;}void helper(int pos){if(poscpnums.size()){vv.push_back(v);return;}for(int i0;icpnums.size();i){if(!vis[i]){v.push_back(cpnums[i]);vis[i]true;helper(pos1);vis[i]false;v.pop_back();}}}
};
方法二
排列和组合不同排列与元素顺序相关交换数字能够得到不同的排列生成全排列的过程就是交换输入集合中元素的顺序以得到不同的排列。
class Solution {
public:vectorvectorint vv;vectorint cpnums;int n;vectorvectorint permute(vectorint nums) {cpnumsnums;ncpnums.size();helper(0);return vv;}void helper(int pos){if(posn){vectorint v;for(int x:cpnums)v.push_back(x);vv.push_back(v);}else{for(int ipos;in;i){Swap(cpnums[pos],cpnums[i]);helper(pos1);Swap(cpnums[pos],cpnums[i]);}}}void Swap(int* a,int* b){int tmp*a;*a*b;*btmp;}
};
包含重复元素集合的全排列
题目 分析
如果集合中有重复的数字那么交换集合中重复的数字得到的全排列是同一个全排列例如交换[1,1,2]中的两个数字1并不能得到新的全排列。
为了便于解决有重复元素会出现相同排列问题先将数组的元素进行排序。
方法一 易知以红色区域为根节点的子树应该剪掉但是以绿色区域为根节点的子树是正确的那么怎么区分二者那
通过观察不难发现绿色区域中目前已填的元素a与前一个元素相同且前一个元素已经被访问过了但是红色区域中目前已填的元素与前一个元素相同但是前一个元素没有被访问过这个点就是突破口。
以nums为例判断条件为 i0 nums[i]nums[i-1] !vis[i-1] 。
class Solution {
public:vectorvectorint vv;vectorint v;vectorint cpnums;bool vis[10]{false};int n;vectorvectorint permuteUnique(vectorint nums) {cpnumsnums;ncpnums.size();sort(cpnums.begin(),cpnums.end());helper(0);return vv;}void helper(int pos){if(posn){vv.push_back(v);return;}for(int i0;in;i){if(!vis[i]){if(i0 cpnums[i]cpnums[i-1] !vis[i-1]) continue;v.push_back(cpnums[i]);vis[i]true;helper(pos1);vis[i]false;v.pop_back();}}}
};
方法二
class Solution {
public:vectorvectorint vv;int n;vectorint cpnums;bool vis[10];vectorvectorint permuteUnique(vectorint nums) {sort(nums.begin(),nums.end());cpnumsnums;ncpnums.size();helper(0);return vv;}void helper(int pos){if(posn){vectorint v;for(int x:cpnums)v.push_back(x);vv.push_back(v);return;}else{setint st;for(int ipos;in;i){if(!st.count(cpnums[i])){st.emplace(cpnums[i]);Swap(cpnums[pos],cpnums[i]);helper(pos1);Swap(cpnums[pos],cpnums[i]);}}}}void Swap(int* a,int* b){int tmp*a;*a*b;*btmp;}
};
该方法不同于方法一除了是通过交换不同位置的元素之外在解决重复元素会出现相同全排列问题上使用set将已访问的元素进行统计当与要访问的元素相等的元素已经被访问过那么访问该元素没问题但是与要访问的元素相等的元素没有被访问过那么就会出现相同的全排列因此这一点就是突破口其实思想还是和方法一解决的突破点一样。
用回溯法解决其它类型的问题
生成匹配的括号
题目 分析
如果输入n,那么生成的括号组合包含n个左括号和n个右括号。因此生成这样的组合需要2n步每一步生成一个括号每一步都面临两个选项既可能生成左括号又可能生成右括号。由此看来这个问题很适合用回溯法解决。
在生成括号组合时需要注意每一步都要满足限制条件。第一个限制条件是左括号或右括号的树木不能唱过n个。第二个限制条件是括号的匹配原则即在任意步骤中已经生成的右括号的数目不能唱过左括号的数目。
代码
class Solution {
public:vectorstring v;string s;vectorstring generateParenthesis(int n) {helper(n,n);return v;}void helper(int left,int right){if(left0 right0){v.push_back(s);return;}if(left0){s(;helper(left-1,right);s.pop_back();}if(rightleft){s);helper(left,right-1);s.pop_back();}}
};
分割回文子字符串
题目 分析
当处理到字符创中的某个字符时如果包括该字符在内后面还有n个字符那么此时面临n个选项即分割出长度为1的子字符串只包含该字符分割出长度为2的子字符串以此类推分割出长度为n的子字符串由于题目要求分割出来的每个子字符串都是回文的因此需要逐一判断这n个子字符串是不是回文的只有回文子字符串才是符合条件的分割分割出一段回文子字符串之后接着分割后面的字符串。
代码
class Solution {
public:vectorvectorstring ans;vectorstring v;string cps;int n;vectorvectorstring partition(string s) {cpss;ncps.size();helper(0);return ans;}void helper(int start){if(startn){ans.push_back(v);return;}for(int istart;in;i){if(isPalindrome(start,i)){v.push_back(cps.substr(start,i-start1));helper(i1);v.pop_back();}}}bool isPalindrome(int begin,int end){while(beginend){if(cps[begin]!cps[end--])return false;}return true;}
};
恢复IP地址
题目 分析
IP地址的特点一个IP被3个 . 字符分割成4段每段都是从0到255之间的一个数字另外除“0”本身外其他数字不能以‘0’开头。
如果输入的字符串长度为n由于逐一处理字符串中的每个字符因此需要n步并且每一步都面临两个可能的选项由此可见适合用回溯法来解决。
代码
class Solution {
public:bool isValidSeg(string seg){return (stoi(seg) 255) (seg 0 || seg[0] !0);}void helper(string s,int i,int segI,string seg,string ip,vectorstring result){if(is.length() segI 3 isValidSeg(seg))result.push_back(ipseg);else if(is.length() segI 3){char chs[i];if(isValidSeg(segch))helper(s,i1,segI,segch,ip,result);if(seg.length()0 segI3)helper(s,i1,segI1,string(1,ch),ipseg.,result);}}vectorstring restoreIpAddresses(string s) {vectorstring result;helper(s,0,0,,,result);return result;}
};
总结
如果解决一个问题需要若干步骤并且在每一步都面临若干选项那么可以尝试用回溯法解决这个问题。适合用回溯法解决的问题的一个特点是解决这个问题存在多个解而题目往往要求列出所有的解。
采用回溯法能够解决集合的排列组合的很多问题仔细分析这些问题及变种的代码就会发现最终的代码都大同小异都可以采用递归来实现。递归代码需要先确定递归退出的边界条件然后逐个处理集合中的元素。对于组合类问题每个数字都面临两个选项即添加当前数字到组合中或不添加当前数字到组合中。对于排列问题一个数字如果后面有n个数字那么面临n1个选择即可以将该数字和它后面的数字包括它本身交换。根据这些选项做出选择之后再调用递归函数处理后面的数字。
