[dfs入门必看]
题目概述
从 1∼n 这 n个整数中随机选取任意多个,输出所有可能的选择方案。
输入格式
输入一个整数 n。
输出格式
每行输出一种方案。同一行内的数必须升序排列,相邻两个数用恰好 1个空格隔开。
对于没有选任何数的方案,输出空行。
本题有自定义校验器(SPJ),各行(不同方案)之间的顺序任意。
数据范围
1≤ n ≤15
输入样例:
3
输出样例:
3
2
2 3
1
1 3
1 2
1 2 3
- 本题相当于是dfs模型题,重点掌握其思想
- 分析题目
- 从n个数中任意选择任意个,显然用寻常的循环很难解决,上一个数选不选对这个数并无影响,但对结果是有影响的。此时,我们可以考虑用递归来解决
下图就是一颗递归搜索树,也是解决问题的关键- 用 n = 3 举例说明。我们依次判断这3个位置,每个位置上的数数就两种情况,选还是不选,由此我们就画出了类似树的结构
- 用 n = 3 举例说明。我们依次判断这3个位置,每个位置上的数数就两种情况,选还是不选,由此我们就画出了类似树的结构
- 怎样将这个图转化为代码?
- 从n个数中任意选择任意个,显然用寻常的循环很难解决,上一个数选不选对这个数并无影响,但对结果是有影响的。此时,我们可以考虑用递归来解决
- 我们先创建一个状态数组
const int N = 16; int n; int st[N]; // 记录每一位的状态,0表示没考虑,1表示选,2表示不选
2.然后对每一位进行判断
//参数表示当前该考虑哪一位 从第一位开始
void dfs(int u) {
// 临界
if (u > n) {
// 看哪个位置是被选中的,然后输出
for (int i = 1; i <= n; i ++) {
if (st[i] == 1)
printf("%d ",i);// 注意数后的空格
}
cout << endl;
return;
}
// 第一个分支,不选
st[u] = 2;
dfs(u + 1);// 计算下一个位置
st[u] = 0;// 回溯,当前分支计算完后,要将状态恢复
// 第二个分支,选
st[u] = 1;
dfs(u + 1);
st[u] = 0;
}
- 完整代码
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
const int N = 16;
int n;
int st[N]; // 记录每一位的状态,0表示没考虑,1表示选,2表示不选
//参数表示当前该考虑哪一位 从第一位开始
void dfs(int u) {
// 临界
if (u > n) {
for (int i = 1; i <= n; i ++) {
if (st[i] == 1)
printf("%d ",i);
}
cout << endl;
return;
}
st[u] = 2;
dfs(u + 1);
st[u] = 0;
st[u] = 1;
dfs(u + 1);
st[u] = 0;
}
int main() {
cin >> n;
dfs(1);
return 0;
}
- 本题结束,图和思想是重点,理清后,代码写一遍就会了
对本题还有疑问的话可以打在评论区,别忘了点赞和收藏!