递归
例题1：集合的划分
代码：
#include<iostream>
using namespace std;
long long dfs(int n,int k){
if(n<k||k==0) return 0;
if(n==k||k==1)return 1;
return dfs(n-1,k-1)+k*dfs(n-1,k);
}
int main(){
int n,k;
cin>>n>>k;
cout<<dfs(n,k);
return 0;
}【题目解析】
在放第n个数时有两种情况，一为并入前面k个集合中，情况有k*dfs（n-1，k）种，二为自成一个集合，情况为dfs（n-1,k-1）种，所以所有的情况就为dfs(n-1,k-1)+k*dfs(n-1,k)种。
例题2：逆波兰表达式
代码：
#include<iostream>
#include<iomanip>
#include<bits/stdc++.h>
using namespace std;
char a[10010];
double f(){
scanf("%s",&a);
if(a[0]=='*')return f()*f();
else if(a[0]=='/')return f()/f();
else if(a[0]=='+')return f()+f();
else if(a[0]=='-')return f()-f();
else{
return atof(a);
}
}
int main(){
cout<<fixed<<setprecision(6)<<f();
return 0;
}【题目解析】
通过定义没有参数的函数来获取输入并对输入进行操作，分别对读入的字符型数据进行处理，如果为符号则不断向后层递归，如果为数字则利用atof函数转换为浮点型数据再进行运算。
补充拓展：
atof与atoi：
头文件：#include<stdlib.h>
atof（字符数据）——》double双精度浮点数据
atoi（字符数据）——》int整型数据
例题3：全排列（字母）
代码：
#include<iostream>
using namespace std;
string a,b;
int k;
bool vis[10];
void dfs(int m){
if(m==k){
for(int i=0;i<k;i++){
cout<<b[i];
}
cout<<endl;
}
else{
for(int i=0;i<k;i++){
if(!vis[i]){
vis[i]=1;
b[m]=a[i];
dfs(m+1);
vis[i]=0;
}
}
}
}
int main(){
cin>>a;
k=a.size();
dfs(0);
}【题目解析】
dfs深搜，回溯。
附题：全排列（字母）
代码：
#include<iostream>
using namespace std;
int a[10],n;
bool vis[10];
void dfs(int x){
if(x==n+1){
for(int i=1;i<=n;i++){
printf("%5d",a[i]);
}
cout<<endl;
}
else{
for(int i=1;i<=n;i++){
if(!vis[i]){
a[x]=i;
vis[i]=1;
dfs(x+1);
vis[i]=0;
}
}
}
}
int main(){
cin>>n;
dfs(1);
return 0;
}例题4：数的计数
代码：
#include<iostream>
#include<bits/stdc++.h>
using namespace std;
int cnt=0,h[1010];
void dfs(int x){
if(h[x]!=-1)return ;
h[x]=1;
for(int i=1;i<=x/2;i++){
dfs(i);
h[x]=h[x]+h[i];
}
}
int main(){
memset(h,-1,sizeof(h));
int n;
cin>>n;
dfs(n);
cout<<h[n];
return 0;
}【题目解析】
从1到x/2不断遍历深搜，h数组记录已经计算过的当前数的情况，优化了时间复杂度。
补充拓展：
memset（）：
头文件#include<string>
memset（a,0,sizeof(a)）使数组a的所有元素初始化为0。
搜索与回溯
搜索与回溯是计算机解题中常用的算法，很多问题无法根据某种确定的计算法则来求解，可以利用搜索与回溯的技术求解。回溯是搜索算法中的一种控制策略。它的基本思想是：为了求得问题
的解，先选择某一种可能情况向前探索，在探索过程中，一旦发现原来的选择是错误的，就退回 一步重新选择，继续向前探索，如此反复进行，直至得到解或证明无解。
例题1：素数环
题目简介：
素数环:从1到20这20个数摆成一个环，要求相邻的两个数的和是一个素数
代码：
#include<iostream>
using namespace std;
int n,a[25],cnt=0;
bool vis[25];
bool ss(int x){
bool fl=1;
for(int i=2;i<=n/i;i++){
if(x%i==0){
return 0;
}
}
return fl;
}
void dfs(int m){
if(m==n+1&&ss(a[m]+a[1])){
cnt++;
for(int i=1;i<=n;i++){
cout<<a[i]<<" ";
}
cout<<endl;
}
else{
for(int i=2;i<=n;i++){
if(!vis[i]&&ss(a[m-1]+i)){
a[m]=i;
vis[i]=1;
dfs(m+1);
vis[i]=0;
}
}
}
}
int main(){
cin>>n;
a[1]=1;
vis[1]=1;
dfs(2);
cout<<cnt;
return 0;
}【题目分析】
分析：
因为1~20摆成一个环总数太多，我们选择1~10，并且第一个位置我们定为1。
例题2：自然数的拆分
代码：
#include<iostream>
using namespace std;
int a[10];
int n;
void dfs(int m,int s){
if(s==0){
cout<<n<<"="<<a[1];
for(int i=2;i<m;i++){
cout<<"+"<<a[i];
}
cout<<endl;
}else{
for(int i=1;i<n;i++){
if(i>=a[m-1]&&(i<=s-i||s==i)){
a[m]=i;
dfs(m+1,s-i);
}
}
}
}
int main(){
cin>>n;
dfs(1,n);
return 0;
}【题目解析】
if(i>=a[m-1]&&(i<=s-i||s==i))：
例题3：八皇后问题
代码：
#include<iostream>
#include<bits/stdc++.h>
using namespace std;
int a[20],cnt=0;
bool b[20],zx[20],yx[20];
void dfs(int i){
if(i==9){
cnt++;
cout<<"No."<<" "<<cnt<<endl;
for(int i=1;i<=8;i++){
for(int j=1;j<=8;j++){
if(a[j]==i)cout<<"1"<<" ";
else cout<<"0"<<" ";
}
cout<<endl;
}
}else{
for(int j=1;j<=8;j++){
if(!b[j]&&!zx[i+j]&&!yx[i-j+8]){
a[i]=j;
b[j]=1;
zx[i+j]=1;
yx[i-j+8]=1;
dfs(i+1);
b[j]=0;
zx[i+j]=0;
yx[i-j+8]=0;
}
}
}
}
int main(){
dfs(1);
// cout<<cnt;
return 0;
}【题目解析】
例题4：马的遍历
例题5：选数
代码：
#include<iostream>
using namespace std;
int n,k,a[30],cnt=0;
bool ss(int x){
bool fl=1;
for(int i=2;i<=x/i;i++){
if(x%i==0){
fl=0;
break;
}
}
return fl;
}
void dfs(int l,int m,int s){
if(m==k+1){
if(ss(s))cnt++;
}else{
for(int i=l;i<=n;i++){
dfs(i+1,m+1,s+a[i]);
}
}
}
int main(){
cin>>n>>k;
for(int i=1;i<=n;i++){
cin>>a[i];
}
dfs(1,1,0);
cout<<cnt;
return 0;
} 【题目解析】
从i+1位不断递归，避免选过的数重新被选。
课后训练：
训练1：LETTERS
代码参考：
#include<iostream>
using namespace std;
int n,m;
int dx[4]={-1,1,0,0};
int dy[4]={0,0,-1,1};
char a[25][25];
bool v[200];
int nmax=-1e9;
void dfs(int s,int x,int y){
if(s>nmax)nmax=s;
for(int i=0;i<=3;i++){
int xx=x+dx[i];
int yy=y+dy[i];
if(!v[a[xx][yy]]&&xx>=1&&xx<=n&&yy>=1&&yy<=m){
v[a[xx][yy]]=1;
dfs(s+1,xx,yy);
v[a[xx][yy]]=0;
}
}
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>a[i][j];
}
}
v[a[1][1]]=1;
dfs(1,1,1);
cout<<nmax;
return 0;
}【题目解析】
一条路深搜，记录经过最多字母数的路径，用bool数组v标记已经走过的字母，避免重复经过。
训练2：迷宫
参考代码：
#include<iostream>
#include<bits/stdc++.h>
using namespace std;
int ha,la,hb,lb,n;
bool v[105][105],fl=0;
char a;
int dx[4]={-1,1,0,0};
int dy[4]={0,0,-1,1};
bool in(int x,int y){
if(x>=0&&x<n&&y>=0&&y<n)return 1;
else return 0;
}
void dfs(int x,int y){
// cout<<" heha"<<x<<y<<endl;
for(int i=0;i<4;i++){
int xx=x+dx[i];
int yy=y+dy[i];
if(in(xx,yy)&&!v[xx][yy]){
v[xx][yy]=1;
if(xx==hb&&yy==lb){
cout<<"YES"<<endl;
fl=1;
break;
}else{
dfs(xx,yy);
}
// v[xx][yy]=0;
}
}
}
int main(){
int k;
cin>>k;
for(int l=1;l<=k;l++){
// cout<<l<<" ";
fl=0;
memset(v,0,sizeof(v));
cin>>n;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
cin>>a;
if(a=='#')v[i][j]=1;
}
}
cin>>ha>>la;
cin>>hb>>lb;
if(v[ha][la]||v[hb][lb]){
cout<<"NO"<<endl;
continue;
}else{
// cout<<"hehahh";
dfs(ha,la);
}
if(!fl){
cout<<"NO"<<endl;
}
}
return 0;
}
【题目解析】
dfs深搜