回溯大法总结

前言

本篇博客将分两步来进行,首先谈谈我对回溯法的理解,然后通过若干道题来进行讲解,最后总结

对回溯法的理解

回溯法可以看做蛮力法的升级版,它在解决问题时的每一步都尝试所有可能的选项,最终找出所以可行的方案。回溯法非常适合解决由多个步骤组成的问题,并且每个步骤都有多个选项,在每一步选择了其中一个选项之后,就进入下一步,然后又会面临新的选项,就这样重复选择,直至最终的状态。

用回溯法解决问题的过程可以形象地用一个树形结构表示,求解问题的每个步骤可以看作树中的一个节点。如果在某一步有n个可能的选项,每个选项是树中的一条边,经过这些边就可以到达该节点的个子节点。

在采用回溯法解决问题时如果到达树形结构的叶节点,就找到了问题的一个解。如果希望找到更多的解,那么还可以回溯到它的父节点再次尝试父节点其它的选项。如果父节点所有可能的选项都已经试过,那么再回溯到父节点的父节点以尝试它的其他选项,这样逐层回溯到树的根节点。因此,采用回溯法解决问题的过程实质上是在树形结构中从根节点开始进行深度优先遍历。通常,回溯法的深度优先遍历用递归代码实现。

由于回溯法是在所有选项形成的树上进行深度优先遍历,如果解决问题的步骤比较多或每个步骤都面临多个选项,那么遍历整棵树将需要较多的时间,如果明确知道某些子树没有必要遍历,那么在遍历的时候应该避开这些子树以优化效率。通常将使用回溯法时避免遍历不必要的子树的方法称为剪枝。

用回溯解决集合的组合,排列问题

组合不看重元素顺序,因此两个集合中元素个数相同,各元素个数相同,这两个集合就是一个组合。

排列看重元素顺序,因此两个集合中元素个数相同,各元素个数相同,但是元素顺序不同的话,这两个集合就是两个不同的排列。

所有子集

题目

分析

以集合【1,2】为例,有两个元素,每个元素都面临选和不选两种选择,树形图如下图所示:

本题中生成一个子集,可分为若干步,并且每一步都面临若干选择,这正是采用回溯法的典型场景。

代码

class Solution {
public:vector<vector<int>> vv;vector<int> v;vector<int> cnums;vector<vector<int>> subsets(vector<int>& nums) {cnums=nums;dfs(0);return vv;}void dfs(int pos){if(pos==cnums.size()){vv.push_back(v);return;}dfs(pos+1);v.push_back(cnums[pos]);dfs(pos+1);v.pop_back();}
};

在回溯到父节点时,清除之前相应的修改,即恢复现场。

包含K个元素的组合

题目

分析

集合的一个组合也是一个子集,因此求集合的组合的过程和求子集的过程是一样的,这个题目较钱一道题只是增加了一个限制条件,即只找出包含K个数字的组合,只需要在前一道题的基础上稍加修改即可,就可以找出所有包含K个数字的组合。

代码

class Solution {
public:vector<vector<int>> vv;vector<int> v;vector<vector<int>> 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(pos<=n){dfs(n,k,pos+1);v.push_back(pos);dfs(n,k,pos+1);v.pop_back();}}
};
允许重复选择元素的组合

题目

分析

这个题目仍然是关于组合的,但组合中的一个数字可以出现任意次,可以以不变应万变,用回溯法来解决这个问题。

能够用回溯法解决的问题都能够分成若干步来解决,每一步都面临若干选择。对于从集合中选取数字组成组合的问题而言,集合中有多少个数字,解决这个问题就需要多少步,每一步都从集合中取出一个下标为i的数字,此时面临两个选择。一个选择是跳过这个数字不将该数字添加到组合中,那么这一步实际上什么都不做,接下来处理下标为i+1的数字。另一个选择是将该数字添加到组合中,由于一个数字可以重复在集合中出现,也就是说,下一步可能再次选择同一个数字,因此下一步仍然处理下标为i的数字。

代码

class Solution {
public:vector<vector<int>> vv;vector<int> v;vector<vector<int>> combinationSum(vector<int>& candidates, int target) {helper(candidates,target,0);return vv;}void helper(vector<int>& candidates, int target,int pos){if(target==0){vv.push_back(v);return;}else if(pos<candidates.size() && target>0){helper(candidates,target,pos+1);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:vector<vector<int>> vv;vector<int> v;vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {sort(candidates.begin(),candidates.end());helper(candidates,target,0);return vv;}void helper(vector<int>& candidates, int target,int pos){if(target==0){vv.push_back(v);return;}else if(pos<candidates.size() && target>0){int next=pos;while(next<candidates.size() && candidates[next]==candidates[pos]) next++;helper(candidates,target,next);v.push_back(candidates[pos]);helper(candidates,target-candidates[pos],pos+1);v.pop_back();}}
};
没有重复元素集合的全排列

题目

分析

假设集合有n个元素,那么生成一个全排列需要n步,当生成排列的第一个数字时会面临n个选项,即n个数字都有可能成为排列的第1个数字,生成排列的第二个数字会面临n-1个选项,即剩下的n-1个数字都有可能成为排列的第2个数字,以此类推。看起来解决这个问题可以分为n步,每一步都面临若干选项,这就是典型的适用回溯法的场景。

方法一

使用一个bool类型数组来标记是否被访问过,每次填写排列的第I个位置时,都从前往后一次遍历没有被访问过的数字,加入排列。

class Solution {
public:vector<vector<int>> vv;vector<int> v;vector<int> cpnums;bool vis[10];vector<vector<int>> permute(vector<int>& nums) {cpnums=nums;helper(0);return vv;}void helper(int pos){if(pos==cpnums.size()){vv.push_back(v);return;}for(int i=0;i<cpnums.size();i++){if(!vis[i]){v.push_back(cpnums[i]);vis[i]=true;helper(pos+1);vis[i]=false;v.pop_back();}}}
};
方法二

排列和组合不同,排列与元素顺序相关,交换数字能够得到不同的排列,生成全排列的过程,就是交换输入集合中元素的顺序以得到不同的排列。

class Solution {
public:vector<vector<int>> vv;vector<int> cpnums;int n;vector<vector<int>> permute(vector<int>& nums) {cpnums=nums;n=cpnums.size();helper(0);return vv;}void helper(int pos){if(pos==n){vector<int> v;for(int x:cpnums)v.push_back(x);vv.push_back(v);}else{for(int i=pos;i<n;i++){Swap(&cpnums[pos],&cpnums[i]);helper(pos+1);Swap(&cpnums[pos],&cpnums[i]);}}}void Swap(int* a,int* b){int tmp=*a;*a=*b;*b=tmp;}
};
包含重复元素集合的全排列

题目

分析

如果集合中有重复的数字,那么交换集合中重复的数字得到的全排列是同一个全排列,例如交换[1,1,2]中的两个数字1并不能得到新的全排列。

为了便于解决有重复元素会出现相同排列问题,先将数组的元素进行排序。

方法一

易知,以红色区域为根节点的子树应该剪掉,但是以绿色区域为根节点的子树是正确的,那么怎么区分二者那?

通过观察不难发现,绿色区域中,目前已填的元素a与前一个元素相同,且前一个元素已经被访问过了,但是红色区域中,目前已填的元素与前一个元素相同,但是前一个元素没有被访问过,这个点就是突破口。

以nums为例,判断条件为  i>0 && nums[i]=nums[i-1] && !vis[i-1] 

class Solution {
public:vector<vector<int>> vv;vector<int> v;vector<int> cpnums;bool vis[10]={false};int n;vector<vector<int>> permuteUnique(vector<int>& nums) {cpnums=nums;n=cpnums.size();sort(cpnums.begin(),cpnums.end());helper(0);return vv;}void helper(int pos){if(pos==n){vv.push_back(v);return;}for(int i=0;i<n;i++){if(!vis[i]){if(i>0 && cpnums[i]==cpnums[i-1] && !vis[i-1]) continue;v.push_back(cpnums[i]);vis[i]=true;helper(pos+1);vis[i]=false;v.pop_back();}}}
};
方法二
class Solution {
public:vector<vector<int>> vv;int n;vector<int> cpnums;bool vis[10];vector<vector<int>> permuteUnique(vector<int>& nums) {sort(nums.begin(),nums.end());cpnums=nums;n=cpnums.size();helper(0);return vv;}void helper(int pos){if(pos==n){vector<int> v;for(int x:cpnums)v.push_back(x);vv.push_back(v);return;}else{set<int> st;for(int i=pos;i<n;i++){if(!st.count(cpnums[i])){st.emplace(cpnums[i]);Swap(&cpnums[pos],&cpnums[i]);helper(pos+1);Swap(&cpnums[pos],&cpnums[i]);}}}}void Swap(int* a,int* b){int tmp=*a;*a=*b;*b=tmp;}
};

该方法不同于方法一,除了是通过交换不同位置的元素之外,在解决重复元素会出现相同全排列问题上,使用set将已访问的元素进行统计,当与要访问的元素相等的元素已经被访问过,那么访问该元素没问题,但是与要访问的元素相等的元素没有被访问过,那么就会出现相同的全排列,因此这一点就是突破口,其实思想还是和方法一解决的突破点一样。

用回溯法解决其它类型的问题
生成匹配的括号

题目

分析

如果输入n,那么生成的括号组合包含n个左括号和n个右括号。因此生成这样的组合需要2n步,每一步生成一个括号,每一步都面临两个选项,既可能生成左括号又可能生成右括号。由此看来,这个问题很适合用回溯法解决。

在生成括号组合时需要注意每一步都要满足限制条件。第一个限制条件是左括号或右括号的树木不能唱过n个。第二个限制条件是括号的匹配原则,即在任意步骤中已经生成的右括号的数目不能唱过左括号的数目。

代码

class Solution {
public:vector<string> v;string s;vector<string> generateParenthesis(int n) {helper(n,n);return v;}void helper(int left,int right){if(left==0 && right==0){v.push_back(s);return;}if(left>0){s+='(';helper(left-1,right);s.pop_back();}if(right>left){s+=')';helper(left,right-1);s.pop_back();}}
};
分割回文子字符串

题目

分析

当处理到字符创中的某个字符时,如果包括该字符在内后面还有n个字符,那么此时面临n个选项,即分割出长度为1的子字符串(只包含该字符),分割出长度为2的子字符串,以此类推,分割出长度为n的子字符串由于题目要求分割出来的每个子字符串都是回文的,因此需要逐一判断这n个子字符串是不是回文的,只有回文子字符串才是符合条件的分割,分割出一段回文子字符串之后,接着分割后面的字符串。

代码

class Solution {
public:vector<vector<string>> ans;vector<string> v;string cps;int n;vector<vector<string>> partition(string s) {cps=s;n=cps.size();helper(0);return ans;}void helper(int start){if(start==n){ans.push_back(v);return;}for(int i=start;i<n;i++){if(isPalindrome(start,i)){v.push_back(cps.substr(start,i-start+1));helper(i+1);v.pop_back();}}}bool isPalindrome(int begin,int end){while(begin<end){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,vector<string>& result){if(i==s.length() && segI == 3 && isValidSeg(seg))result.push_back(ip+seg);else if(i<s.length() && segI <=3){char ch=s[i];if(isValidSeg(seg+ch))helper(s,i+1,segI,seg+ch,ip,result);if(seg.length()>0 && segI<3)helper(s,i+1,segI+1,string(1,ch),ip+seg+".",result);}}vector<string> restoreIpAddresses(string s) {vector<string> result;helper(s,0,0,"","",result);return result;}
};
总结

如果解决一个问题需要若干步骤,并且在每一步都面临若干选项,那么可以尝试用回溯法解决这个问题。适合用回溯法解决的问题的一个特点是解决这个问题存在多个解,而题目往往要求列出所有的解。

采用回溯法能够解决集合的排列,组合的很多问题,仔细分析这些问题及变种的代码就会发现最终的代码都大同小异,都可以采用递归来实现。递归代码需要先确定递归退出的边界条件,然后逐个处理集合中的元素。对于组合类问题,每个数字都面临两个选项,即添加当前数字到组合中或不添加当前数字到组合中。对于排列问题,一个数字如果后面有n个数字,那么面临n+1个选择,即可以将该数字和它后面的数字(包括它本身)交换。根据这些选项做出选择之后再调用递归函数处理后面的数字。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/331017.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

从0开始实现一个博客系统 (SSM 实现)

相关技术 Spring Spring Boot Spring MVC MyBatis Html Css JS pom 文件我就不放出来了, 之前用的 jdk8 做的, MySQL 用的 5.7, 都有点老了, 你们自己看着配版本就好 实现功能 用户注册 - 密码加盐加密 (md5 加密)前后端用户信息存储 - 令牌技术用户登录 - (使用 拦截…

Xilinx(AMD) FPGA通过ICAP原语读取芯片IDCODE实现方法

1 概述 Xilinx每种型号的FPGA芯片都有一个唯一的IDCODE与之对应&#xff0c;同一型号不同封装的IDCODE是相同的。IDCODE的获取方法包括JTAG、ICAP原语、AXI_HWICAP IP核等。获取IDCODE常用于根据芯片型号改变代码的功能&#xff0c;或者对代码进行授权保护&#xff0c;只能在指…

从《红楼梦》的视角看大模型知识库 RAG 服务的 Rerank 调优

背景介绍 在之前的文章 有道 QAnything 源码解读 中介绍了有道 RAG 的一个主要亮点在于对 Rerank 机制的重视。 从目前来看&#xff0c;Rerank 确实逐渐成为 RAG 的一个重要模块&#xff0c;在这篇文章中就希望能讲清楚为什么 RAG 服务需要 Rerank 机制&#xff0c;以及如何选…

现代密码学——消息认证和哈希函数

1.概述 1.加密-->被动攻击&#xff08;获取消息内容、业务流分析&#xff09; 消息认证和数字签名-->主动攻击&#xff08;假冒、重放、篡改、业务拒绝&#xff09; 2.消息认证作用&#xff1a; 验证消息源的真实性&#xff0c; 消息的完整性&#xff08;未被篡改…

集合、Collection接口特点和常用方法

1、集合介绍 对于保存多个数据使用的是数组&#xff0c;那么数组有不足的地方。比如&#xff0c; 长度开始时必须指定&#xff0c;而且一旦制定&#xff0c;不能更改。 保存的必须为同一类型的元素。 使用数组进行增加/删除元素的示意代码&#xff0c;也就是比较麻烦。 为…

分布式数据库HBase入门指南

目录 概述 HBase 的主要特点包括: HBase 的典型应用场景包括: 访问接口 1. Java API: 2. REST API: 3. Thrift API: 4. 其他访问接口: HBase 数据模型 概述 该模型具有以下特点&#xff1a; 1. 面向列: 2. 多维: 3. 稀疏: 数据存储: 数据访问: HBase 的数据模型…

你真的会使用Vue3的onMounted钩子函数吗?Vue3中onMounted的用法详解

目录 一、onMounted的前世今生 1.1、onMounted是什么 1.2、onMounted在vue2中的前身 1.2.1、vue2中的onMounted 1.2.2、Vue2与Vue3的onMounted对比 1.3、vue3中onMounted的用法 1.3.1、基础用法 1.3.2、顺序执行异步操作 1.3.3、并行执行多个异步操作 1.3.4、执行一次…

基于STM32实现智能光照控制系统

目录 引言环境准备智能光照控制系统基础代码示例&#xff1a;实现智能光照控制系统 光照传感器数据读取PWM控制LED亮度用户界面与显示应用场景&#xff1a;智能家居与农业自动化问题解决方案与优化收尾与总结 1. 引言 本教程将详细介绍如何在STM32嵌入式系统中使用C语言实现智…

纯代码如何实现WordPress搜索包含评论内容?

WordPress自带的搜索默认情况下是不包含评论内容的&#xff0c;不过有些WordPress网站评论内容比较多&#xff0c;而且也比较有用&#xff0c;所以想要让用户在搜索时也能够同时搜索到评论内容&#xff0c;那么应该怎么做呢&#xff1f; 网络上很多教程都是推荐安装SearchWP插…

数据结构----堆的实现(附代码)

当大家看了鄙人的上一篇博客栈后&#xff0c;稍微猜一下应该知道鄙人下一篇想写的博客就是堆了吧。毕竟堆栈在C语言中常常是一起出现的。那么堆是什么&#xff0c;是如何实现的嘞。接下来我就带大家去尝试实现一下堆。 堆的含义 首先我们要写出一个堆&#xff0c;那么我们就需…

基于地理坐标的高阶几何编辑工具算法(4)——线分割面

文章目录 工具步骤应用场景算法输入算法输出算法示意图算法原理 工具步骤 选中待分割面&#xff0c;点击“线分割面”工具&#xff0c;绘制和面至少两个交点的线&#xff0c;双击结束&#xff0c;执行分割操作 应用场景 快速切分大型几何面&#xff0c;以降低面的复杂度&…

数据结构篇其三---链表分类和双向链表

​ 前言 数据结构篇其二实现了一个简单的单链表&#xff0c;链表的概念&#xff0c;单链表具体实现已经说明&#xff0c;如下&#xff1a; 单链表 事实上&#xff0c;前面的单链表本质上是无头单向不循环链表。此篇说明的双向链表可以说完全反过来了了。无论是之前的单链表还…

ElasticSearch - 删除已经设置的认证密码(7.x)

文章目录 Pre版本号 7.x操作步骤检查当前Elasticsearch安全配置停止Elasticsearch服务修改Elasticsearch配置文件删除密码重启Elasticsearch服务验证配置 小结 Pre Elasticsearch - Configuring security in Elasticsearch 开启用户名和密码访问 版本号 7.x ES7.x 操作步骤 …

从ES到ClickHouse,Bonree ONE平台更轻更快!

本文字数&#xff1a;8052&#xff1b;估计阅读时间&#xff1a;21 分钟 作者&#xff1a;博睿数据 李骅宸&#xff08;太道&#xff09;& 娄志强&#xff08;冬青&#xff09; 本文在公众号【ClickHouseInc】首发 本系列第一篇内容&#xff1a; 100%降本增效&#xff01;…

01-02.Vue的常用指令(二)

01-02.Vue的常用指令&#xff08;二&#xff09; 前言v-model&#xff1a;双向数据绑定v-model举例&#xff1a;实现简易计算器Vue中通过属性绑定为元素设置class 类样式引入方式一&#xff1a;数组写法二&#xff1a;在数组中使用三元表达式写法三&#xff1a;在数组中使用 对…

redis--redis Cluster

简介 解决了redis单机写入的瓶颈问题&#xff0c;即单机的redis写入性能受限于单机的内存大小、并发数量、网卡速率等因素无中心架构的redis cluster机制&#xff0c;在无中心的redis集群当中&#xff0c;其每个节点保存当前节点数据和整个集群状态,每个节点都和其他所有节点连…

数组和指针的联系(C语言)

数组和指针是两种不同的数据类型&#xff0c;数组是一种构造类型&#xff0c;用于存储一组相同类型的变量&#xff1b;而指针是一种特殊类型&#xff0c;专门用来存放数据的地址。数组名除了sizeof(数组名)和&数组名表示整个数组外&#xff0c;其他情况下都表示的是首元素的…

百度集团:AI重构,走到哪了?

内有自家公关一号“自曝”狼性文化&#xff0c;主动制造舆论危机。 外有&#xff0c;OpenAI、谷歌、字节、华为等大模型劲敌扎堆迭代新产品&#xff0c; 强敌环伺。 今天我们要说的是早就从BAT掉队的——百度。 最近&#xff0c;在武汉Aapollo Day 2024上&#xff0c;百度发布了…

增强ev代码签名证书2300

代码签名证书是软件开发者们确保软件完整性和安全性的重要工具之一。在各种类型的代码签名证书中&#xff0c;增强EV代码签名证书拥有许多独特的功能而受到企业开发者的欢迎&#xff0c;今天就随SSL盾小编了解增强EV代码签名证书的申请条件以及申请流程。 1.增强型EV代码签名证…

npm介绍、常用命令详解以及什么是全局目录

目录 npm介绍、常用命令详解以及什么是全局目录一、介绍npm的主要功能npm仓库npm的配置npm的版本控制 二、命令1. npm init: 初始化一个新的Node.js项目&#xff0c;创建package.json文件。package.json是一个描述项目信息和依赖关系的文件。2. npm install <package_name&g…