递归实现指数型枚举
从 $1∼n$ 这 $n$ 个整数中随机选取任意多个,输出所有可能的选择方案。
输入格式
输入一个整数 $n$
输出格式
每行输出一种方案。
同一行内的数必须升序排列,相邻两个数用恰好 $1$ 个空格隔开。
对于没有选任何数的方案,输出空行。
本题有自定义校验器(SPJ),各行(不同方案)之间的顺序任意。
数据范围
$1\leqslant n\leqslant 15 $
输入样例:
输出样例:
1 2 3 4 5 6 7 8
| 3 2 2 3 1 1 3 1 2 1 2 3
|
解析
两种方法,状态压缩和正常的递归dfs
首先讲第一种,对前面最短Hamilton路径理解了的,就很好想
因为 $1≤n≤15$ ,所以可以枚举所有的情况,总共只有 $2^{15}$ 种情况,即只有 $32768$ 种情况
然后输出第 $k$ 位为 $1$ 的 $k$ 即可。
代码
1 2 3 4 5 6 7 8 9 10 11 12 13
| #include <cstdio> #include <iostream>
int n;
int main() { scanf("%d", &n); for (int i = 0; i < 1 << n; i++) { for (int j = 0; j < n; j++) { if(i >> j & 1) printf("%d ", j + 1); } printf("\n"); } return 0; }
|
然后是第二种,简单的遍历所有拿还是不拿的情况
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28
| #include <cstdio> #include <cstring> #include <iostream>
const int N = 20; int a[N];
int n;
void dfs(int k) { if(k == n + 1) { for (int i = 1; i <= n; i++) { if(a[i] == 1) printf("%d ", i); } printf("\n"); return ; } dfs(k + 1); a[k] = 1; dfs(k + 1); a[k] = 0; }
int main() { scanf("%d", &n); dfs(1); return 0; }
|