题目描述
92 93 94 求解1代码
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
92
#include<bits/stdc++.h>
using namespace std;
const int N=15;
int state[N];
int n;
void dfs(int v){
if(v==n){
for(int i=0;i<n;i++)
if(state[i]==1)
cout<<i+1<<" ";
cout<<endl;
return;
}
state[v]=1;//选择该位置
dfs(v+1);
state[v]=2;//不选择该位置
dfs(v+1);
state[v]=0;
}
int main(){
cin>>n;
dfs(0);
return 0;
}
93
#include<bits/stdc++.h>
using namespace std;
const int N=15;
int n,m;//cn m
int way[N];//存储单个序列
void dfs(int v,int start){//已经选择的个数,以及将要开始选择的数据
if(v+n-start+1<m)//剪枝操作,已选个数n + 可选个数n-start+1 < 要选个数m 时剪枝
return;
if(v==m){//边界条件
for(int i=0;i<m;i++)
printf("%d ",way[i]);
puts("");
// cout<<way[i]<<" ";
// cout<<endl;
return;
}
for(int i=start;i<=n;i++){//升序选择
way[v]=i;
dfs(v+1,i+1);
}
}
int main(){
// cin>>n>>m;
scanf("%d%d",&n,&m);
dfs(0,1);
return 0;
}
94
#include<bits/stdc++.h>
using namespace std;
const int N=9;
int n;
bool used[N];
int state[N];
void dfs(int v){
if(v==n){
for(int i=0;i<n;i++)
cout<<state[i]<<" ";
cout<<endl;
return;
}
for(int i=0;i<n;i++){
if(used[i]==false){
state[v]=i+1;
used[i]=true;
dfs(v+1);
state[v]=0;
used[i]=false;
}
}
}
int main(){
cin>>n;
dfs(0);
return 0;
}