Description
从 1~n 这 n 个整数中随机选出 m 个，输出所有可能的选择方案。,,。
两个整数 n，m。
Output
按照从小到大的顺序输出所有方案，每行 1 个。首先，同一行内的数升序排列，相邻两个数用一个空格隔开。其次，对于两个不同的行，对应下标的数一一比较，字典序较小的排在前面（例如 1 3 9 12 排在 1 3 10 11 前面）。
Sample Output
1
2
3
4
5
6
7
8
9
10
| 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
|
Limit
| Time Limit | Memory Limit |
|---|
| 1 秒（C/C++/Rust/Pascal），2 秒（其他语言） | 32 M（C/C++/Rust/Pascal），64 M（其他语言） |
Analysis
同 CH0301 递归实现指数型枚举，不过本题需要分析一下数据范围：
由题目条件,,：
再结合，对固定的，有
要让的取值区间非空，必须，再结合，得到。分段写出：
总之，若均为整数，数据范围可总结为：
其中最大为，最大也为（此时）。
补充，为了表达的方便，本文在之后的时间复杂度分析中参数会用代替
Solve
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
29
30
31
32
33
34
35
36
37
| #include <iostream>
const int N = 30;
int n, m, st[N];
int ans[N], idx;
void dfs(int p, int cnt) {
if(cnt == m)
for(int i = 0; i < idx; ++i)
std::cout << ans[i] << ' ';
if(cnt == m) std::cout << '\n';
for(int i = p + 1; i <= n; ++i) {
if(!st[i]) {
st[i] = 1;
ans[idx++] = i;
dfs(i, cnt + 1);
st[i] = 0;
--idx;
}
}
}
int main () {
std::ios::sync_with_stdio(0);
std::cin.tie(0);
std::cin >> n >> m;
for(int i = 1; i <= n; ++i) {
st[i] = 1;
ans[idx++] = i;
dfs(i, 1);
st[i] = 0;
--idx;
}
}
|
时间复杂度依然为
Ex
如果要求使用非递归方法，该怎么做呢？
嗯，因为最大为，最大也为，可以想到状态压缩的思路：
枚举从到的状态，对每个状态，根据技巧快速判断其中的的数目是否为，若是，则按顺序遍历该状态的每一个比特，当比特位为一时输出对应序号。时间复杂度依然为，代码实现如下：
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
29
30
31
32
33
| #include <iostream>
const int N = 25;
int n, m;
int getBitNum(int i) {
int cnt = 0;
while(i) {
++cnt;
i ^= i & (-i);
}
return cnt;
}
void display(int x) {
for(int i = 0; i < N; ++i) {
if(x & 1 << i) std::cout << i + 1 << ' ';
}
std::cout << '\n';
}
int main () {
std::ios::sync_with_stdio(0);
std::cin.tie(0);
std::cin >> n >> m;
for(int i = 0; i < 1 << n; ++i) {
if(getBitNum(i) == m) {
display(i);
}
}
}
|
但是这个代码实现不能通过题目，因为题目有输出顺序要求「按照从小到大的顺序输出所有方案」，一个简单的想法是额外空间存储这些符合条件的状态，对这些状态自定义排序（即），最后再统一输出：
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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
| #include <iostream>
#include <algorithm>
const int N = 25;
int n, m;
int st[1 << N], idx;
int getBitNum(int i) {
int cnt = 0;
while(i) {
++cnt;
i ^= i & (-i);
}
return cnt;
}
void display(int x) {
for(int i = 0; i < N; ++i) {
if(x & 1 << i) std::cout << i + 1 << ' ';
}
std::cout << '\n';
}
int main () {
std::ios::sync_with_stdio(0);
std::cin.tie(0);
std::cin >> n >> m;
for(int i = 0; i < 1 << n; ++i) {
if(getBitNum(i) == m) {
st[idx++] = i;
}
}
std::sort(st, st + idx, [](int a, int b) {
for (int j = 0; j < n; ++j)
if (((a >> j) & 1) != ((b >> j) & 1)) return (a >> j) & 1;
return 0;
});
for(int i = 0; i < idx; ++i) display(st[i]);
return 0;
}
|
其中：
1
2
3
4
5
6
| for(int i = 0; i < 1 << n; ++i) {
if(getBitNum(i) == m) {
st[idx++] = i;
}
}
|
这个部分是
1
2
3
4
5
| std::sort(st, st + idx, [](int a, int b) {
for (int j = 0; j < n; ++j)
if (((a >> j) & 1) != ((b >> j) & 1)) return (a >> j) & 1;
return 0;
});
|
这个部分是
1
| for(int i = 0; i < idx; ++i) display(st[i]);
|
这个部分是
综上，代码的时间复杂度为
Ref
