网站开发语言识别,设计logo的方法,高级搜索百度,wordpress搬家_后台错乱#我们在DFS的搜索学习中涉及到了回溯的操作#xff0c;那什么是回溯呢#xff1f;
就是说我们在标记数组之后#xff0c;我们进行解标记的操作#xff0c;同时再次进入递归#xff0c;出现新的情况的操作#xff0c;这就叫做回溯操作。 如果现在有这样一道题#xff1a…#我们在DFS的搜索学习中涉及到了回溯的操作那什么是回溯呢
就是说我们在标记数组之后我们进行解标记的操作同时再次进入递归出现新的情况的操作这就叫做回溯操作。 如果现在有这样一道题abc如何输出他的全部排列方式这时候我们就可以用回溯操作来解决这样的问题;
回溯与搜索
分为以下几个步骤
1.枚举方案数
2.标记-防止重复搜索
3.搜索当前层
4.进入下一层去搜索下个方案
5.回溯解标记
6.终止条件
第一步中有枚举方案数
void dfs(int dep)
{//1.枚举方案数 for(int i0;is.size();i){
第二步标记-防止重复搜索
if(!vis[i]) {vis[i]1;
第三步搜索当前层
//3.搜索当前层 ans[dep]s[i];
第四步进入下一层去搜索下个方案
//4.进入下一层去搜索下个方案dfs(dep1);
第五步回溯解标记 //5.回溯vis[i]0;
第六步终止条件 //6.终止条件if(deps.size()1){//前面s.size已经搜索完了//搜多少打印多少 for(int i1;idep;i) coutans[i];coutendl;return;}
综合起来我们的回溯操作模板就是这样的
#includebits/stdc.h
using namespace std;
bool vis[101];
char ans[101];
string s;
void dfs(int dep)
{//1.枚举方案数 for(int i0;is.size();i){//6.终止条件if(deps.size()1){//前面s.size已经搜索完了//搜多少打印多少 for(int i1;idep;i) coutans[i];coutendl;return;} //2.标记-防止重复搜索 if(!vis[i]) {vis[i]1;//3.搜索当前层 ans[dep]s[i];//4.进入下一层去搜索下个方案dfs(dep1); //5.回溯vis[i]0;}}} int main(){cins;dfs(1);return 0;} //谢谢大家的支持啦~~
