AcWing 93. 递归实现组合型枚举
原题链接
简单
作者:
stdin_5
,
2025-02-04 21:58:54
,
所有人可见
,
阅读 1
#include <bits/stdc++.h>
using namespace std;
int n, m;
const int N = 26;
int st[N];
bool used[N];
void dfs(int u) {
if(u+n-st[u-1]<m)return;//伟大的剪枝,使得时间减少一半(从250到102)
if (u > m) {
for (int i = 1; i <= m; i++)
cout << st[i] << " ";//根据记录状态输出
cout << endl;
return;//边界条件,忘记写这个会导致内存访问出错,从而形成Segmentation Fault
}
for (int i = 1+st[u - 1]; i <= n; ++i) {
if (!used[i]) {
//这边条件的筛选多加一个比上一个数大,因为这次数组计算从1开始,所以u=1时刚好访问到st[0],不用担心内存问题。这边从遍历时直接筛选掉,有种剪枝的感觉。
used[i] = true, st[u] = i;
dfs(u + 1);
used[i] = false, st[u] = 0;
}
}
}
int main() {
cin >> n >> m;
dfs(1);
}