Loading... 从 `1∼n` 这 `n` 个整数中随机选出 `m` 个，输出所有可能的选择方案。 ### 输入格式 两个整数 `n` 和 `m`，在同一行用空格隔开。 ### 输出格式 按照从小到大的顺序输出所有方案，每行 `1` 个。 1. 同一行内的数升序排列，相邻两个数用一个空格隔开。 2. 对于两个不同的行，对应下标的数一一比较，字典序较小的排在前面（例如 `1 3 5 7` 排在 `1 3 6 8` 前面）。 ### 数据范围 * `n > 0` * `0 ≤ m ≤ n` * `n + (n - m) ≤ 25` ### 输入样例 ``` 5 3 ``` ### 输出样例 ``` 1 2 3 1 2 4 1 2 5 1 3 4 1 3 5 1 4 5 2 3 4 2 3 5 2 4 5 3 4 5 ``` **思考题** 如果要求使用非递归方法，该怎么做呢？ ### 题目分析 DFS ### 代码实现 ``` #include <iostream> #include <bitset> #include <vector> using namespace std; const int N = 30; int n, m; bitset <N> bt; vector <int> ans; void dfs(int pre) { if (bt.count() == m) { for (const auto& i : ans) cout << i << ' '; cout << '\n'; return ; } for (int i = pre + 1; i <= n; ++i) { if (!bt[i]) { bt[i] = 1; ans.push_back(i); dfs(i); ans.erase(ans.end() - 1); bt[i] = 0; } } } int main () { ios::sync_with_stdio(0); cin.tie(0); cin >> n >> m; dfs(0); return 0; } ``` 最后修改：2023 年 09 月 23 日 © 允许规范转载 赞 如果觉得我的文章对你有用，请随意赞赏