题目描述
从 1∼n这 n个整数中随机选出 m个,输出所有可能的选择方案。
样例
5 3
算法1
(递归) $O(n^2)$
找了两个参数来记录选了多少个和放弃多少个,c代表已经选了,fa代表已经放弃多少个
然后输出判断就可以分为两种情况
1.是全部选完了就输出,如123,124等
2.是剩下的不得不选,如125,235等
于是条件1即为c==m;
条件2即为跳过没选的和最大可以不选的数量一样,即fa=n-m
时间复杂度
不知道
参考文献
无
C++ 代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 26;
int st[N];//1是选中了,2是不选他
int n;
int m;
void put(int u, int m, int c, int fa) {
//选完了的情况
if (c == m) {
for (int i = 0; i < n; i++) {
if (st[i] == 1)
cout << i+1 << " ";
}
cout << endl;
return;
}
//选到最后不得不选了
if (fa == n - m) {
for (int i = 0; i < n; i++) {
if (st[i] == 1)
cout << i+1 << " ";
else if (i >= c + fa)
cout << i+1 << " ";
}
cout << endl;
return;
}
st[u] = 1;
put(u + 1, m, c + 1, fa);
st[u] = 0;
st[u] = 2;
put(u + 1, m, c, fa + 1);
st[u] = 0;
}
int main() {
cin >> n;
cin >> m;
put(0, m, 0, 0);
return 0;
}
第一次写题解,有点小激动,写的不好请见谅。