递归/深度优先搜索
92. 递归实现指数型枚举 - AcWing题库
指数型递归指的是给定的数组中的每个数都有x种选择，那么时间复杂度就为x的n次方,在这道题中,1-n的每个数字都有两张选择,选或不选。那么本题的时间复杂度就是2的n次方，方案数也是2的n次方,这是指数递归问题。
2的15次方为32768远远小于1e8,可以使用指数递归解决。
/*
* @Date: 2024-02-07 14:58:30
* @LastEditors: lanziking
* @LastEditTime: 2024-02-07 15:11:21
* @FilePath: \algorithm\a92.cpp
*/
#include<iostream>
using namespace std;
const int N = 20;
int n,q[N];
//x代表了有x个数字已经完成了选择,count代表数组有效的元素个数
void dfs(int x,int count)
{
if(x > n)
{
for(int i = 0;i < count;i ++)
{
cout << q[i] << " ";
}
cout << endl;
return;
}
//选这个数
q[count] = x;
dfs(x + 1,count + 1);
//不选这个数
dfs(x + 1,count);
}
int main()
{
cin >> n;
dfs(1,0);
return 0;
}
选的话会把count + 1传给下一层，而后不选会把count传给下一层。所以之前的 q[count] = x;对不选是没有影响的，因为不会访问到。选和不选是可以交换位置的。
P1706 全排列问题 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
一共有n个坑位，第一个坑有n种选择，第二个有n - 1，所以这题递归的时间复杂度为n * n！, 9 * 9！= 3265920，小于1e8。这是排列递归问题。
排列问题需要使用st[N]状态数组来记录数字的状态，用于判断该数字是否使用过。
/*
* @Date: 2024-02-14 16:52:39
* @LastEditors: lanziking
* @LastEditTime: 2024-02-14 17:04:13
* @FilePath: \algorithm\p1706_2.cpp
*/
#include<iostream>
#include<iomanip>
using namespace std;
//排列问题需要使用uesd数组来记录这个数字是否使用过。
//x代表了已经选择出多少个数字了
//要格式对齐时,setw要放在前面。
const int N = 11;
int q[N],n;
bool used[N];
void dfs(int x)
{
if(x == n)
{
for(int i = 0;i < n;i ++)
{
cout << setw(5) << q[i] ;
}
cout << endl;
//return不写也可以，因为此时used数组全为true。但还是要写上。养成习惯。
return;
}
for(int i = 1;i <= n;i ++)
{
if(!used[i])
{
used[i] = true;
q[x] = i;
dfs(x + 1);
used[i] = false;
}
}
}
void slove()
{
cin >> n;
dfs(0);
}
int main()
{
slove();
return 0;
}
P1157 组合的输出 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
组合与排列不同，组合中 1 2 3与3 2 1是等价的。我们通过观察答案发现在组合答案中，数字是递增的。所以我们给排列加上一个递增条件就是组合。可以不适用st数组。
/*
* @Date: 2024-02-14 17:07:07
* @LastEditors: lanziking
* @LastEditTime: 2024-02-14 17:20:29
* @FilePath: \algorithm\p1157_2.cpp
*/
#include<iostream>
#include<iomanip>
//从五个数字中选出三个数字的组合 那么1 2 3 和3 2 1就属于是一共情况
//观察答案发现答案总是升序排列的，所以我们只需要控制一下寻找的起点就可以了。
using namespace std;
const int N = 22;
int n,r,q[N];
//x代表找到的数字数量,m代表下一层寻找的起点。
void dfs(int x,int m)
{
if(x == r)
{
for(int i = 0;i < r;i ++)
{
cout << setw(3)<< q[i];
}
cout << endl;
//组合的return是必须的，不写死循环。
return;
}
for(int i = m;i <= n;i ++)
{
q[x] = i;
//当前层选择了i 下一层从i + 1开始选择。
dfs(x + 1,i + 1);
}
}
void slove()
{
cin >> n >> r;
dfs(0,1);
}
int main()
{
slove();
return 0;
}
[P1036 NOIP2002 普及组] 选数 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
组合 + 额外判断
从n个数中找到k个数的组合，判断这个组合的和是否是素数，如果是，res++。
/*
* @Date: 2024-02-14 17:22:45
* @LastEditors: lanziking
* @LastEditTime: 2024-02-14 17:55:30
* @FilePath: \algorithm\p1036_2.cpp
*/
#include<iostream>
#include<cmath>
using namespace std;
const int N = 1e6 + 10;
int k,n,q[N],res;//从n个数字中找k个,共有res种组合的和为素数。
bool is_su(int x)
{
if(x == 1 || x == 0)return false;
for (int i = 2; i <= sqrt(x); i++)
{
if(x % i == 0)return false;
}
return true;
}
void dfs(int x,int m,int sum)
{
if(k == x)
{
if(is_su(sum))
res ++;
return;
}
for(int i = m;i < n;i ++)
{
//sum + q[i]才可以。
dfs(x + 1,i + 1,sum + q[i]);
}
}
//要求和为素数的组合。那就在组合的dfs函数上加一个sum参数来判断。
void slove()
{
cin >> n >> k;
for(int i = 0;i < n;i ++)
{
cin >> q[i];
}
//开始是0个数字,从q数组的第0个元素开始,元素和为0;
dfs(0,0,0);
cout << res ;
}
int main()
{
slove();
return 0;
}
P2089 烤鸡 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
这是一道指数级问题，每个配料有三种选择1 2 3。n最大为30。方案数最大为3的十次方 59049。所以用来存方案的数组s长度为6e5。
每种调料有三种选择，对调料的选择进行dfs满足条件就存入s数组，不满足不存后面会覆盖掉不满足的方案。
/*
* @Date: 2024-02-14 17:57:10
* @LastEditors: lanziking
* @LastEditTime: 2024-02-14 20:18:45
* @FilePath: \algorithm\p2089_3.cpp
*/
#include<iostream>
using namespace std;
const int N = 14;
int n,count;
//答案数组要开大一点
string ans[90000];
string s;
//x代表到了第几个坑位,sum代表剩余的美味程度
void dfs(int x,int sum)
{
if(x == 10 || sum == 0)
{
if(x == 10 && sum == 0)
{
for(int i = 0;i < 10;i ++)
{
ans[count][i] = s[i];
}
count ++;
}
return;
}
for(int i = 1;i <= 3;i ++)
{
s[x] = '0' + i;
dfs(x + 1,sum - i);
}
}
void slove()
{
cin >> n;
//第0个坑位开始,美味程度一开始为n。
dfs(0,n);
cout << count << endl;
for(int i = 0;i < count;i ++)
{
for(int j = 0;j < 10;j ++)
{
cout << ans[i][j] <<" ";
}
cout << endl;
}
}
int main()
{
slove();
return 0;
}
[P1088 NOIP2004 普及组] 火星人 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
这题使用的是排列dfs,当获得指定序列号需要exit退出，因为后面的结果对这个题没什么影响。
/*
* @Date: 2024-02-08 20:13:47
* @LastEditors: lanziking
* @LastEditTime: 2024-02-08 22:44:08
* @FilePath: \algorithm\p1088_2.cpp
*/
#include<iostream>
#include<math.h>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N = 1e4 + 10;
int q[N],n,m,res,ans[N];
bool st[N];
void dfs(int x)
{
if(x > n){
res ++;
if(res == m + 1)
{
for(int i = 1;i <= n;i ++)
{
cout << ans[i] << " ";
}
exit(0);
}
return;
}
for(int i = 1;i <= n;i ++)
{
//给i赋初值,从q[i]给定的值开始递归
if(res == 0) i = q[x];
if(!st[i])
{
st[i] = true;
ans[x] = i;
dfs(x + 1);
st[i] = false;
}
}
}
int main()
{
cin >> n >> m;
for (int i = 1; i <= n; i++)
{
cin >> q[i];
}
dfs(1);
return 0;
}
// 1 2 3 4 5
// 1 2 3 5 4
// 1 2 4 3 5
// 1 2 4 5 3
[P1149 NOIP2008 提高组] 火柴棒等式 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
这提示指数搜索，一共三个位置，每个位置有N种选择。复杂度为N的三次方。
/*
* @Date: 2024-02-09 11:29:42
* @LastEditors: lanziking
* @LastEditTime: 2024-02-09 12:29:09
* @FilePath: \algorithm\p1149_2.cpp
*/
#include<iostream>
using namespace std;
const int N = 775;
//74 + 0 = 74
int sticks[N] = {6,2,5,5,4,5,6,3,7,6},n,res,q[4];
void dfs(int x,int s)
{
if(x == 3 || s == 0)
{
if(x == 3 && s == 0)
{
if(q[0] + q[1] == q[2])res ++;
}
return;
}
for(int i = 0;i < 775;i ++)
{
q[x] = i;
dfs(x + 1,s-sticks[i]);
}
}
int main()
{
cin >> n;
for(int i = 10;i < 775;i ++)
{
sticks[i] = sticks[i / 10] + sticks[i % 10];
}
dfs(0,n - 4);
cout << res;
return 0;
}
[P2036 COCI2008-2009 #2] PERKET - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
这个题也是指数级枚举，因为每种调料有选或不选两种选择，一共有2的n次方种绝对差值。
/*
* @Date: 2024-02-14 21:06:24
* @LastEditors: lanziking
* @LastEditTime: 2024-02-14 21:22:50
* @FilePath: \algorithm\p2036_3.cpp
*/
#include<iostream>
using namespace std;
const int N = 15;
//枚举所有的食材总和。每个食材有选和不选两种选择。
int s[N],b[N],res = 1000000,n;
void dfs(int x,int si,int bi)
{
//x == n也就是所有物品都有选择的时候跳出递归
if(x == n)
{
if(si != 1 && bi != 0)
{
res = min(res,abs(si - bi));
}
return ;
}
dfs(x + 1,si * s[x],bi + b[x]);
dfs(x + 1,si,bi);
}
void slove()
{
cin >> n;
for(int i = 0;i < n;i ++)
{
cin >> s[i] >> b[i];
res = min(res,abs(s[i] - b[i]));
}
dfs(0,1,0);
cout << res << endl;
}
int main()
{
slove();
return 0;
}
P1683 入门 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
/*
* @Date: 2024-02-15 10:29:08
* @LastEditors: lanziking
* @LastEditTime: 2024-02-15 11:02:57
* @FilePath: \algorithm\p1683_2.cpp
*/
#include<iostream>
using namespace std;
const int N = 23;
int dx[] = {-1,1,0,0},dy[] = {0,0,-1,1},w,h,sx,sy,res;
char g[N][N];
bool used[N][N];
//每个位置只走一次，不用恢复现场，因为重复踩一个块他只算一次。一直向前走，不回头走到头就可以算出最大的块数。
void dfs(int x,int y)
{
res ++;
for(int i = 0;i < 4;i ++)
{
int xi = x + dx[i];
int yi = y + dy[i];
if(xi >= 1 && xi <= w && yi >= 1 && yi <= h && g[xi][yi] == '.' && !used[xi][yi])
{
used[xi][yi] = true;
dfs(xi,yi);
}
}
}
void slove()
{
cin >> h >> w;
for(int i = 1;i <= w;i ++)
{
for(int j = 1;j <= h;j ++)
{
cin >> g[i][j];
if(g[i][j] == '#')
{
used[i][j] = true;
}
if(g[i][j] == '@')
{
sx = i;
sy = j;
}
}
}
dfs(sx,sy);
cout << res << endl;
}
int main()
{
slove();
return 0;
}
P1605 迷宫 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
/*
* @Date: 2024-02-15 12:01:41
* @LastEditors: lanziking
* @LastEditTime: 2024-02-15 12:42:45
* @FilePath: \algorithm\p1605_2.cpp
*/
#include<iostream>
using namespace std;
const int N = 7;
int n,m,t,sx,sy,fx,fy,res,dx[] = {-1,1,0,0},dy[] = {0,0,-1,1};
bool used[N][N];
void dfs(int x,int y)
{
if(x == sx && y == sy)
{
res ++;
//找到起点说明找到了一条路径,res ++，结束继续向下递归。
return;
}
for(int i = 0;i < 4;i ++)
{
int xi = x + dx[i];
int yi = y + dy[i];
if(xi >= 1 && yi >= 1 && xi <= n && yi <= m && !used[xi][yi])
{
used[xi][yi] = true;
dfs(xi,yi);
used[xi][yi] = false;
}
}
}
void slove()
{
cin >> n >> m >> t;
cin >> sx >> sy >> fx >> fy;
//要将重点设置为走过，否则会造成走回来的路线，也就是走重复块。
for(int i = 0;i < t;i ++)
{
int x,y;
cin >> x >> y;
//障碍物与使用过数组为同一个
used[x][y] = true;
}
if(used[fx][fy])
{
cout << 0 << endl;
return;
}
else{
used[fx][fy] = true;
}
dfs(fx,fy);
cout << res <<endl;
}
int main()
{
slove();
return 0;
}
[P1596 USACO10OCT] Lake Counting S - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
#include<iostream>
using namespace std;
const int N = 105;
int n,m,res,dx[] = {-1,-1,-1,0,0,1,1,1},dy[] = {1,0,-1,1,-1,1,0,-1};
char g[N][N];
bool used[N][N];
void change(int x,int y)
{
if(g[x][y] == '.')
{
return ;
}
g[x][y] = '.';
for(int i = 0;i < 8;i ++)
{
int xi = x + dx[i];
int yi = y + dy[i];
if(xi >= 1 && yi >= 1 && xi <= n && yi <= m && g[xi][yi] == 'W')
{
//不需要使用uesd数组，因为当遍历到g[i][j]时会把他的值从w编程.。边改边寻找。
change(xi,yi);
}
}
}
void slove()
{
cin >> n >> m;
for(int i = 1;i <= n;i ++)
{
for(int j = 1;j <= m;j ++)
{
cin >> g[i][j];
}
}
for(int i = 1;i <= n;i ++)
{
for(int j = 1;j <= m;j ++)
{
if(g[i][j] == 'W')
{
res ++;
change(i,j);
}
}
}
cout << res << endl;
}
int main()
{
slove();
return 0;
}
P1451 求细胞数量 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
/*
* @Date: 2024-02-15 17:26:06
* @LastEditors: lanziking
* @LastEditTime: 2024-02-15 18:16:36
* @FilePath: \algorithm\p1451_2.cpp
*/
#include<iostream>
using namespace std;
const int N = 105;
int n,m,res,dx[] = {1,-1,0,0},dy[] = {0,0,-1,1};
char g[N][N];
void change(int x,int y)
{
if(g[x][y] == '0')return;
g[x][y] = '0';
for(int i = 0;i < 4;i ++)
{
int xi = x + dx[i];
int yi = y + dy[i];
if(xi >= 1 && yi >= 1 && xi <= n && yi <= m && g[xi][yi] != '0')
{
change(xi,yi);
}
}
}
void slove()
{
cin >> n >> m;
// cout << n << endl;
// cout << m << endl;
for(int i = 1;i <= n;i ++)
{
for(int j = 1;j <= m;j ++)
{
cin >> g[i][j];
}
}
for(int i = 1;i <= n;i ++)
{
for(int j = 1;j <= m;j ++)
{
if(g[i][j] != '0')
{
res ++;
change(i,j);
}
}
}
cout << res << endl;
}
int main()
{
slove();
return 0;
}
1114. 棋盘问题 - AcWing题库
/*
* @Date: 2024-02-15 18:18:05
* @LastEditors: lanziking
* @LastEditTime: 2024-02-15 22:43:42
* @FilePath: \algorithm\a1114_2.cpp
*/
#include<iostream>
using namespace std;
const int N = 100;
bool flag = true,stx[N],sty[N];
int n,k,count,res,dx[] = {-1,-1,1,1},dy[] = {-1,1,-1,1},sx[N],sy[N];//sx与sy用来存储#的坐标 count记录数目
//指数级 每个#都可以选择放或者不放
//x代表还剩余几个#没有被选择出来，m代表到了第几个#进行选择(选 or 不选)
void dfs(int x,int m)
{
//所有数字都能放下。
if(x == 0)
{
res ++;
return;
}
if(x < 0 || m >= count) return;
dfs(x,m + 1);//m位置的#不选
if(!stx[sx[m]] && !sty[sy[m]])
{
stx[sx[m]] = true;
sty[sy[m]] = true;
dfs(x - 1,m + 1);//这个位置的#满足条件可以选择
stx[sx[m]] = false;
sty[sy[m]] = false;//恢复现场
}
}
void slove()
{
cin >> n >> k;
//记得将res置0
if(n == -1 && k == -1)
{
flag = false;
exit(0);
return;
}
for(int i = 1;i <= n;i ++)
{
for(int j = 1;j <= n;j ++)
{
char c;
cin >> c;
if(c == '#')
{
sx[count] = i;
sy[count ++] = j;
}
}
}
dfs(k,0);
// cout << k << endl;
cout << res << endl;
count = 0;
res = 0;
}
int main()
{
while(flag)
{
slove();
}
return 0;
}
// 1785
// 1332
// 6 4
// ##..##
// ..####
// #####.
// ####..
// .#####
// ###.##
// 6 4
// #.####
// ######
// #.####
// ...#..
// ######
// ##.##.
// -1 -1
[P1025 NOIP2001 提高组] 数的划分 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
/*
* @Date: 2024-02-15 23:01:27
* @LastEditors: lanziking
* @LastEditTime: 2024-02-15 23:10:29
* @FilePath: \algorithm\p1025_3.cpp
*/
#include<iostream>
using namespace std;
//类似于组合 但不完全是组合下一层的数字大于等于上一层的数字。
int n,k,res;
//x代表选择了几个数字，sum代表数字的总和，s代表下一层的起点
//在递归时要进行优化,只枚举到n - sum即可。
void dfs(int x,int sum,int s)
{
if(x == k || sum == n)
{
if(x == k && sum == n) res ++;
return;
}
for(int i = s;i <= n - sum;i ++)
{
dfs(x + 1,sum + i,i);
}
}
void slove()
{
cin >> n >> k;
dfs(0,0,1);
cout << res << endl;
}
int main()
{
slove();
return 0;
}
[P1019 NOIP2000 提高组] 单词接龙 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
#include<iostream>
#include<string>
using namespace std;
const int N = 25;
int n;
int g[N][N],cnt[N],res;//g[i][j]代表第i个单词的后面可以接j的最小长度。cnt用来记录每个单词接过的数量。
string s[N];
char flag;
void dfs(string p,int x)//p代表字符串拼接后的值，x代表这次拼上的字符串的下标。
{
res = max(int(p.size()),res);
cnt[x] ++;
for(int i = 0;i < n;i ++)
{
if(g[x][i] != 0 && cnt[i] < 2)
{
dfs(p + s[i].substr(g[x][i]),i);//将下标为i的字符串拼到x后面，需要截取掉公共部分在拼接
}
}
cnt[x] --;//记得用完恢复现场
}
void slove()
{
cin >> n;
for(int i = 0;i < n;i ++)
{
cin >> s[i];
}
cin >> flag;
//预处理出g数组
for(int i = 0;i < n;i ++)
{
for(int j = 0;j < n;j ++)
{
for(int k = 1;k < min(s[i].size(),s[j].size());k ++)
{
if(s[i].substr(s[i].size() - k) == s[j].substr(0,k))
{
g[i][j] = k;
break;
}
}
}
}
for(int i = 0;i < n;i ++)
{
if(s[i][0] == flag)
{
dfs(s[i],i);
}
}
cout << res << endl;
}
int main()
{
slove();
return 0;
}
