题目大意
输入$n$,$m$,从$1$到$n$中选$m$个数,输出所有方案。同一行内升序,行与行间字典序从小到大。
解题思路
依然按位置考虑,因为要求行内升序,dfs需要多关心一个状态,当前要选的数至少要大于等于什么。st数组也因此省去,不需要回溯。
具体代码
#include<iostream>
using namespace std;
const int N=15;
int n,m;
int path[N];
void dfs(int u,int start) //当前正考虑第u个位置,要选的数至少大于等于start
{
if(u==m+1) //已考虑完所有位置
{
for(int i=1;i<=m;i++)
cout<<path[i]<<' ';
puts("");
return;
}
for(int i=start;i<=n;i++)
{
path[u]=i;
dfs(u+1,i+1);
path[u]=0; //这条命令没用,只是为了对称美观
}
}
int main()
{
cin>>n>>m;
dfs(1,1);
return 0;
}