本文主要是介绍DFS(排列数字、飞机降落、选数、自然数的拆分)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
注：1.首先要知道退出条件
2.还原现场
典型：全排列
题目1：
代码：
#include<bits/stdc++.h>
using namespace std;
int a[1005],p[1005],v[1005];
int n;
void dfs(int x)
{//此次dfs结束条件,即搜到底 if(x==n+1){for(int i=1;i<=n;i++)cout<<p[i]<<" "; cout<<endl;return ;}for(int i=1;i<=n;i++){if(!v[a[i]])//若该数字未访问 {p[x]=a[i];//记录该数字v[a[i]]=1;dfs(x+1);//搜索下一个位置 v[a[i]]=0; //上面搜索完之后，回溯 }}
}
int main()
{cin>>n;for(int i=1;i<=n;i++)a[i]=i;dfs(1);return 0;} 题目2：P9241 [蓝桥杯 2023 省 B] 飞机降落 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
代码（含解析）：
#include<bits/stdc++.h>
using namespace std;
int n;
int t[15],d[15],l[15],v[15];
int flag;//标记该是否有满足条件的降落顺序
void dfs(int preTime,int x)//preTime用于记录上一架飞机降落完毕的时间，x用于记录当前降落飞机数量
{if(x==n+1)//此时所有飞机降落完成，退出 {flag=1;return;}for(int i=1;i<=n;i++) {if(v[i]==0&&preTime<=t[i]+d[i])//若当前飞机还未访问且当前飞机油未耗尽，当前飞机可为下一个降落的飞机 {v[i]=1;//已访问 dfs(max(t[i],preTime)+l[i],x+1);//访问这轮dfs的下一个节点 v[i]=0;//还原现场 }}
}
int main()
{int T;cin>>T;while(T--){flag=0; cin>>n;for(int i=1;i<=n;i++)cin>>t[i]>>d[i]>>l[i];dfs(0,1);//可理解为上一架飞机降落时间为0，此时寻找第一架降落飞机 if(flag==1)cout<<"YES"<<endl;elsecout<<"NO"<<endl;}return 0;
}题目3：P1036 [NOIP2002 普及组] 选数 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
代码（含解析）：
#include<bits/stdc++.h>
using namespace std;
int a[25],v[25];
int n,k;
int ans;
bool isPrime(int x)//判断是否为素数
{if(x<=3)return x>1;for(int i=2;i<=sqrt(x);i++){if(x%i==0)return false;}return true;
}
//cnt代表选了多少个数，sum为cnt个数的和，st代表从哪个数开始
void dfs(int cnt,int sum,int st)
{if(cnt==k+1)//若已经选完了k个数（sum为K个数的和） {if(isPrime(sum))ans++;}for(int i=st;i<=n;i++){if(v[i]==0){v[i]=1;dfs(cnt+1,sum+a[i],i+1);v[i]=0;}}
}
int main()
{cin>>n>>k;for(int i=1;i<=n;i++)cin>>a[i];dfs(1,0,1);cout<<ans;return 0;} 题目4： P2404 自然数的拆分问题 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
代码：
#include<bits/stdc++.h>
using namespace std;
int n;
int p[1000];
//sum记录当前数的和，cnt代表当前要找第cnt个数，st代表当前从几开始加
void dfs(int sum,int cnt,int st)
{if(sum>n) return;//退出条件 if(sum==n) {// cnt代表当前找的数的个数，当前找到的为cnt-1个数 for(int i=1;i<=cnt-2;i++)cout<<p[i]<<"+";cout<<p[cnt-1]<<endl;return;}for(int i=st;i<=n-1;i++){p[cnt]=i;//记录路径 dfs(sum+i,cnt+1,i);}
}
int main()
{cin>>n;dfs(0,1,1);return 0;} 这篇关于DFS(排列数字、飞机降落、选数、自然数的拆分)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
