AcWing 93. 递归实现组合型枚举(非递归)
原题链接
简单
作者:
3_54
,
2024-11-17 17:46:37
,
所有人可见
,
阅读 1
#include <bits/stdc++.h>
using namespace std;
struct State
{
int u; // 当前正在选择第几个数
int start; // 当前选择范围起点
int i; // 表示栈内部的循环状态
};
int n, m;
int way[100];
int main()
{
cin >> n >> m;
stack<State> stk;
// 初始状态:选择第一个数,从1开始选择
stk.push({1, 1, 1});
while (!stk.empty())
{
State t = stk.top();
stk.pop();
// 剪枝:若剩余的数不够用,直接跳过
if (t.u + n - t.start + 1 < m)
{
continue;
}
// 如果已选够m个数,输出当前路径
if (t.u > m)
{
for (int i = 1; i <= m; i++)
{
cout << way[i] << ' ';
}
cout << endl;
continue;
}
if (t.i <= n)
{
way[t.u] = t.i;
stk.push({t.u, t.start, t.i + 1}); // 把当前栈放回去并将其i + 1表示进入下一个循环
stk.push({t.u + 1, t.i + 1, t.i + 1}); // 下一层递归
}
}
return 0;
}