何为深搜?
即不撞南墙不罢休。
话不多说,直接看题:
我们可以把这看成深搜的模板题,下面是AC代码:
#include<bits/stdc++.h>
using namespace std;
int a[15];//存值并输出
int vis[15];
int n=18;
void dfs(int deep){
if(deep>n){
for(int i=1;i<=n;i++) cout<<a[i]<<" ";
cout<<endl;
}
else{
for(int i=1;i<=n;i++){
if(vis[i]==0){
a[deep]=i;
vis[i]=1;
dfs(deep+1);
a[deep]=0;
vis[i]=0;
}
}
}
}
int main(){
dfs(1);
}
加点难度:
输出n个数中选m个的组合
其实,我们只要在原先基础上限定从小到大的顺序并且限定个数即可。
下面是AC代码:
法1.
#include<bits/stdc++.h>
using namespace std;
int a[15];//存值并输出
int vis[15];
int n=5;
int m=3;
void dfs(int deep){
if(deep>m){
for(int i=1;i<=m;i++) cout<<a[i]<<" ";
cout<<endl;
}
else{
for(int i=1;i<=n;i++){
if(vis[i]==0&&i>a[deep-1]){
a[deep]=i;
vis[i]=1;
dfs(deep+1);
a[deep]=0;
vis[i]=0;
}
}
}
}
int main(){
dfs(1);
}
法2.
#include<bits/stdc++.h>
using namespace std;
int a[15];//存值并输出
int vis[15];
int n=5;
int m=3;
void dfs(int deep,int last){
if(deep>m){
for(int i=1;i<=m;i++) cout<<a[i]<<" ";
cout<<endl;
}
else{
for(int i=last+1;i<=n;i++){
if(vis[i]==0){
a[deep]=i;
vis[i]=1;
dfs(deep+1,i);
a[deep]=0;
vis[i]=0;
}
}
}
}
int main(){
dfs(1,0);
}