方法一：增量构造法
#include<cstdio>
#include<iostream>
using namespace std;
void print(int n,int *a,int cur){
printf("(");
for(inti=0;i<cur;i++)
printf("%d",a[i]);
puts(")");
intm=cur?a[cur-1]+1:0;//避免cur==0时程序崩溃
for(inti=m;i<n;i++){
a[cur]=i;
print(n,a,cur+1);
}
}
int main(){
inta[10000]={0};
intn;
cin>>n;
print(n,a,0);
return0;
}
方法二：位向量法（不是按字典序输出）
枚举每一位选或者不选，复杂度比方法一略高但更好理解，因为与输出全排列思路差不多，满n位就输出。
#include<cstdio>
#include<iostream>
using namespace std;
int vis[1000]={0};
void print(int n,int *a,int cur){
if(cur==n){
printf("( ");
for(inti=0;i<n;i++)
if(vis[i])printf("%d ",i);
puts(")");
}
else{
vis[cur]=1;
print(n,a,cur+1);
vis[cur]=0;
print(n,a,cur+1);
}
}
int main(){
inta[10000]={0};
intn;
cin>>n;
print(n,a,0);
return0;
}
方法三：二进制法 方法二其实与二进制是对应的。
#include<cstdio>
#include<iostream>
using namespace std;
void print(int n){
for(inti=0;i<(1<<n);i++){
printf("(");
for(intj=0;j<n;j++)
if(i&(1<<j))printf("%d ",j);
puts(")");
}
}
int main(){
inta[1000],n;
cin>>n;
print(n);
return0;
}
