递归实现指数型枚举对于每个数字只有选或者不选,因此从小到大遍历即可,枚举选或者不选,使用二进制数字保存选择状态,在枚举完最后一个数字的时候输出
#include<iostream>
using namespace std;
int n;
//对于每个数只有选或者不选
void dfs(int u,int state){
if(u==n){
for(int i=0;i<n;i++)
if(state>>i&1) printf("%d ",i+1);
puts("");
return;
}
dfs(u+1,state|1<<u);
dfs(u+1,state);
}
int main(){
cin>>n;
dfs(0,0);
return 0;
}
递归实现组合型枚举,和指数型枚举本质上相同,只不过需要多一个sum记录当前已经选择的数字数量,当为m时输出state的状态即可
#include<iostream>
using namespace std;
int n,m;
//sum是state中1的个数,u是当前枚举到的数字
void dfs(int u,int state,int sum){
if(sum+n-u<m) return;
if(sum==m){
for(int i=0;i<n;i++)
if(state>>i&1) printf("%d ",i+1);
puts("");
return;
}
dfs(u+1,state|1<<u,sum+1);
dfs(u+1,state,sum);
}
int main(){
cin>>n>>m;
dfs(0,0,0);
return 0;
}
与前两种稍有不同,需要借助回溯的思想,依次遍历所有可选择数字中的未选择部分。每次递归时都遍历所有可选择数组,依次选择,没有不选的情况,使用vector保存,回溯现场。
#include<iostream>
#include<vector>
using namespace std;
vector<int> path;
int n;
void dfs(int u,int state){
if(u==n){
for(auto c:path) printf("%d ",c);
puts("");
return ;
}
for(int i=0;i<n;i++){
if(!(state>>i&1)){
path.push_back(i+1);
dfs(u+1,state|1<<i);
path.pop_back();
}
}
}
int main(){
cin>>n;
dfs(0,0);
return 0;
}