算法1
递归暴搜
#include <bits/stdc++.h>
using namespace std;
const int N = 100;
int n, m;
int a[N];
void dfs(int start, int u)
{
if(u == m)
{
for(int i = 1; i <= m; i ++ )
cout << a[i] << ' ';
cout << endl;
return ;
}
for(int i = start; i <= n; i ++ )
{
a[u + 1] = i;
dfs(i + 1, u + 1);
}
}
int main()
{
cin >> n >> m;
dfs(1, 0);
}
算法2 O(2^n * n)
二进制枚举1的个数为1的数,记录下来后排序达到字典序最小
#include <bits/stdc++.h>
using namespace std;
const int N = 1e7;
int n, m;
int a[N];
string s[N];
int main()
{
cin >> n >> m;
int u = 0;
for(int i = 0; i < 1 << n; i ++ )
{
int cnt = 0;
for(int j = 0; j < n; j ++ )
if(i >> j & 1) a[ ++ cnt] = j + 1;
if(cnt == m)
{
for(int j = 1; j <= cnt; j ++ )
s[u] += a[j];
u ++ ;
}
}
sort(s, s + u);
for(int i = 0; i < u; i ++ )
{
for(int j = 0; j < m; j ++ )
cout << int(s[i][j]) << ' ';
cout << endl;
}
}