题目描述:
从 1∼n 这 n 个整数中随机选取任意多个,输出所有可能的选择方案。
输入格式:
输入一个整数 n。
输出格式:
每行输出一种方案。
同一行内的数必须升序排列,相邻两个数用恰好 1 个空格隔开。
对于没有选任何数的方案,输出空行。
本题有自定义校验器(SPJ),各行(不同方案)之间的顺序任意。
数据范围:
1≤n≤15;
输入样例:
3
输出样例:
3
2
2 3
1
1 3
1 2
1 2 3
分析步骤:
第一:理清思路:
-
我们这道题还是DFS去求解,但是这道题目要我们求解的是指数型枚举,所以和组合型,排列型不一样。大家要明白组合和排列和指数型的区别。我们求解DFS有两种方法,一种是枚举位置;一种是枚举数字。本题采用枚举位置的方法,因为这个更简单跟容易理解。
-
枚举位置,我们先枚举第一个位置他有四种选择:不选,1,2,3这样我们就可以像一颗树一样去画出来。如果选了就标记一下这个数已经选过了,如果不选则放弃这个数再向后去寻找是否选择其他的数。这样我们每次都有两个选择,慢慢向下去搜索我们会发现这是一颗递归搜索树。大家可以动手画一画,看看是否和我一样。
第二:书写主函数,构建整体框架:
-
输入值,进入DFS这个1代表我们已经遍历到了第几个位置。书写DFS我们一定要明白,自己对于变量的定义是什么,只有明白了我们在之后的递归中才不会迷失。
int main()
{
cin>>n;
dfs(1);
return 0;
}
第三:书写DFS函数
-
我们一般先写结束条件,如果我们的x>n就代表所有的数都经过了选择,我们就按顺序把那些选过的标记了的输出出来就可以。
-
我们先假设他不选就将状态改为false再去向下递归,这样搜索一遍之后返回,再假设选择这个数再去递归,这样就可以保证所有的可能都在这里面了。
void dfs(int x){
if(x>n){
for(int i = 1 ; i <= n ; i ++){
if(st[i]) cout<<i<<" ";
}
cout<<endl;
return ;
}
st[x] = false;
dfs(x+1);
st[x] = true;
dfs(x+1);
}
代码:
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 20;
bool st[N];
int n ;
void dfs(int x){
if(x>n){
for(int i = 1 ; i <= n ; i ++){
if(st[i]) cout<<i<<" ";
}
cout<<endl;
return ;
}
st[x] = false;
dfs(x+1);
st[x] = true;
dfs(x+1);
}
int main()
{
cin>>n;
dfs(1);
return 0;
}
注意:递归实现排列型枚举;递归实现组合型枚举;递归实现指数型枚举。这三道题目代表了DFS三大标准题型,学会这三道模板题目才有可能继续去学习更难的DFS。