题目链接:
题意: 从 n 个数中选取数字, 输出所有的选取可能
idea: 枚举所有取数可能, 就一简单的 DFS, 不过题解用二进制表示状态, 着实巧妙
我的 DFS:
- #include <iostream>
- #include <cstdio>
- using namespace std;
- const int N = 16;
- int n, a[16];
- bool st[16];
- void dfs(int num)
- {
- if (num> n)
- {
- for (int i = 1; i <= n; i ++ )
- if (st[i]) cout <<i << " ";
- cout << endl;
- return;
- }
- st[num] = true;
- dfs(num + 1);
- st[num] = false;
- dfs(num + 1);
- }
- int main()
- {
- cin>> n;
- dfs(1);
- return 0;
- }
- View Code
大佬 (秦淮岸) 的位运算 + 递归深度优先搜索
用一个数的二进制的每一位表示选取状态
- #include <bits/stdc++.h>
- using namespace std;
- int n;
- void dfs(int x,int now)
- {
- if (x>n)
- return ;
- if (x==n)
- {
- for (int i=1;i<=n;i++)
- if (now>>(i-1) & 1)
- cout<<i<<" ";
- puts("");
- }
- dfs(x+1,now<<1 | 1);
- dfs(x+1,now<<1);
- }
- int main()
- {
- cin>>n;
- dfs(0,0);
- }
- View Code
来源: http://www.bubuko.com/infodetail-3317217.html