题目描述
从1~n这n个数种随机选取任意多个,输出所有的可能方案
样例
3
3
2
2 3
1
1 3
1 2
1 2 3
----------
算法1
(暴力枚举) $O(2^n)$
参考文献 算法竞赛进阶指南
C++ 代码
这等价于每个整数可以选和不选,所有可能的方案总数共有2^n种,可以用二进制枚举来列举所有选择方案,当然也可以用
递归,时间复杂度会少一点,求解问题的时候注意顺序,先进数组的数一定会更小。观察一下输出,其实输出就是可以这
么看:
0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1
这其实就是一个集合的所有子集。而所有子集的总数为2^n
#include<bits/stdc++.h>
using namespace std;
vector<int>chosen;
int n;
void cal(int cnt){
if(cnt==n+1){
for(int i=0;i<chosen.size();i++)
printf("%d ",chosen[i]);
puts("");
return;
}
for(int i=0;i<2;i++){
if(!i) cal(cnt+1);
else{
chosen.push_back(cnt);
cal(cnt+1);
chosen.pop_back();
}
}
}
int main(){
scanf("%d",&n);
cal(1);
return 0;
}