深度优先搜索题目合集
本片为洛谷题目
纯手打，请您放心食用！
目录
U121029 全排列(可重复)
题目描述
输入格式
输出格式
输入输出样例
题解
P1157 组合的输出
题目描述
输入格式
输出格式
输入输出样例
题解
P2404 自然数的拆分问题
题目描述
输入格式
输出格式
输入输出样例
说明/提示
U121029 全排列(可重复)
题目描述
输入n,从1~n的数可重复的排列：(n<9) 例如：n=3
1 1 1
1 1 2
1 1 3
1 2 1
1 2 2
1 2 3
1 3 1
……
3 3 3
输入格式
输入n
输出格式
输出所有排列。
输入输出样例
输入 #1
3
输出 #1
1 1 1 1 1 2 1 1 3 1 2 1 1 2 2 1 2 3 1 3 1 1 3 2 1 3 3 2 1 1 2 1 2 2 1 3 2 2 1 2 2 2 2 2 3 2 3 1 2 3 2 2 3 3 3 1 1 3 1 2 3 1 3 3 2 1 3 2 2 3 2 3 3 3 1 3 3 2 3 3 3
题解
#include<bits/stdc++.h>
using namespace std;
int n,a[11];
void bfs(int g){
if(g>n){
for(int i=1;i<=n;i++)cout<<a[i]<<" ";
cout<<endl;
return;
}
for(int i=1;i<=n;i++){
a[g]=i;
bfs(g+1);
}
}
int main(){
cin>>n;
bfs(1);
return 0;
}P1157 组合的输出
题目描述
排列与组合是常用的数学方法，其中组合就是从 n 个元素中抽出 r 个元素（不分顺序且 r≤n），我们可以简单地将 n 个元素理解为自然数 1,2,…,n，从中任取 r 个数。
现要求你输出所有组合。
例如 n=5,r=3，所有组合为：
123,124,125,134,135,145,234,235,245,345123,124,125,134,135,145,234,235,245,345。
输入格式
一行两个自然数 n,r(1<n<21,0≤r≤n)。
输出格式
所有的组合，每一个组合占一行且其中的元素按由小到大的顺序排列，每个元素占三个字符的位置，所有的组合也按字典顺序。
注意哦！输出时，每个数字需要 3 个场宽。以 C++ 为例，你可以使用下列代码：
cout << setw(3) << x;
输出占 33 个场宽的数 x。注意你需要头文件 iomanip。
输入输出样例
输入 #1
5 3
输出 #1
1 2 3 1 2 4 1 2 5 1 3 4 1 3 5 1 4 5 2 3 4 2 3 5 2 4 5 3 4 5
题解
#include<bits/stdc++.h>
using namespace std;
int n,r,a[21];
void bfs(int g){
if(g>r){
for(int i=1;i<=r;i++)cout<<setw(3)<<a[i];
cout<<endl;
return;
}
for(int i=a[g-1]+1;i<=n;i++){
a[g]=i;
bfs(g+1);
}
}
int main(){
cin>>n>>r;
bfs(1);
return 0;
}P2404 自然数的拆分问题
题目描述
任何一个大于 11 的自然数 n，总可以拆分成若干个小于 n 的自然数之和。现在给你一个自然数 n，要求你求出 n 的拆分成一些数字的和。每个拆分后的序列中的数字从小到大排序。然后你需要输出这些序列，其中字典序小的序列需要优先输出。
输入格式
输入：待拆分的自然数 n。
输出格式
输出：若干数的加法式子。
输入输出样例
输入 #1
7
输出 #1
1+1+1+1+1+1+1 1+1+1+1+1+2 1+1+1+1+3 1+1+1+2+2 1+1+1+4 1+1+2+3 1+1+5 1+2+2+2 1+2+4 1+3+3 1+6 2+2+3 2+5 3+4
说明/提示
数据保证，2≤n≤8
题解
#include<bits/stdc++.h>
using namespace std;
int n,a[11]={1},sum=0;
void bfs(int g,int sum){
if(sum==n&&g>2){
for(int i=1;i<=g-2;i++)cout<<a[i]<<"+";
cout<<a[g-1]<<endl;
return;
}
for(int i=a[g-1];i<=n-sum;i++){
a[g]=i;
sum+=i;
bfs(g+1,sum);
sum-=i;
}
}
int main(){
cin>>n;
bfs(1,0);
return 0;
}P1706 全排列问题
题目描述
按照字典序输出自然数 11 到 n 所有不重复的排列，即 n 的全排列，要求所产生的任一数字序列中不允许出现重复的数字。
输入格式
一个整数 n。
输出格式
由 1∼n 组成的所有不重复的数字序列，每行一个序列。
每个数字保留 55 个场宽。
输入输出样例
输入 #1
3
输出 #1
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
说明/提示
1≤n≤9。
题解
#include<bits/stdc++.h>
using namespace std;
int n,a[11];
bool f[11];
void bfs(int g){
if(g>n){
for(int i=1;i<=n;i++)cout<<setw(5)<<a[i];
cout<<endl;
return;
}
for(int i=1;i<=n;i++){
if(f[i]==false){
f[i]=true;
a[g]=i;
bfs(g+1);
f[i]=false;
}
}
}
int main(){
cin>>n;
bfs(1);
return 0;
}P1657 选书
题目描述
学校放寒假时，信息学奥赛辅导老师有 1,2,3,⋯,x 本书，要分给参加培训的 x 个人，每人只能选一本书，但是每人有两本喜欢的书。
老师事先让每个人将自己喜欢的书填写在一张表上。然后根据他们填写的表来分配书本，希望设计一个程序帮助老师求出所有可能的分配方案，使每个学生都满意。
输入格式
第 11 行一个数 x。
第 22 行至第 1+x 行，每行两个数，表示 ai 喜欢的书的序号。
输出格式
只有一个数，总方案数 total。
输入输出样例
输入 #1
5 1 3 4 5 2 5 1 4 3 5
输出 #1
2
说明/提示
数据范围及约定
对于全部数据，1≤x≤20。
update 2022/03/07update 2022/03/07，阮行止
本题原始数据中，最后一个数据点的 x 为 0，期望输出为 0。考虑到这个数据不合理，予以删去。现在提交这个题目不会遇到 x=0 的数据点。
题解
#include<bits/stdc++.h>
using namespace std;
int n,a[21],b[21],sum=0;
bool f[21];
void bfs(int g){
if(g>n){
sum++;
return;
}
if(f[a[g]]==false){
f[a[g]]=true;
bfs(g+1);
f[a[g]]=false;
}
if(f[b[g]]==false){
f[b[g]]=true;
bfs(g+1);
f[b[g]]=false;
}
}
int main(){
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i]>>b[i];
bfs(1);
cout<<sum;
return 0;
}P1036 [NOIP2002 普及组] 选数
题目描述
已知 n 个整数 x1,x2,⋯,xn，以及 11 个整数 k（k<n）。从 n 个整数中任选 k 个整数相加，可分别得到一系列的和。例如当 n=4，k=3，44 个整数分别为 3,7,12,193,7,12,19 时，可得全部的组合与它们的和为：
3+7+12=223+7+12=22
3+7+19=293+7+19=29
7+12+19=387+12+19=38
3+12+19=343+12+19=34
现在，要求你计算出和为素数共有多少种。
例如上例，只有一种的和为素数：3+7+19=293+7+19=29。
输入格式
第一行两个空格隔开的整数 n,k（1≤n≤20，k<n）。
第二行 n 个整数，分别为 x1,x2,⋯,xn（1≤xi≤5×10^6）。
输出格式
输出一个整数，表示种类数。
输入输出样例
输入 #1
4 3 3 7 12 19
输出 #1
1
说明/提示
【题目来源】
NOIP 2002 普及组第二题
题解
#include<bits/stdc++.h>
using namespace std;
int n,r,a[21],b[21],c[21],ans=0;
bool func(int n){
if(n<=1)return false;
for(int i=2;i<=sqrt(n);i++)if(n%i==0)return false;
return true;
}
void bfs(int g){
if(g>r){
int temp=0;
for(int i=1;i<=r;i++)temp+=c[i];
ans+=func(temp);
return;
}
for(int i=b[g-1]+1;i<=n;i++){
b[g]=i;
c[g]=a[i];
bfs(g+1);
c[g]=0;
}
}
int main(){
cin>>n>>r;
for(int i=1;i<=n;i++)cin>>a[i];
bfs(1);
cout<<ans;
return 0;
}