递归实现组合型枚举

问题描述

从$1\sim n$的整数中选出$m$个，输出所有的选择方案。

输出格式：对于每种方案，从小到大空格隔开；对于不同的方案，字典序升序输出。

数据范围

• $n>0$
• $0≤m≤n$
• $n+(n−m)≤25$

输入样例

5 3

输出样例

xxxxxxxxxx
1 2 3 
1 2 4 
1 2 5 
1 3 4 
1 3 5 
1 4 5 
2 3 4 
2 3 5 
2 4 5 
3 4 5 

解题思路

类似于递归实现指数型枚举，我们只需要在选取数量恰好是$m$的时候再输出就行了。

但是需要注意的是，数据范围变成了25。所以需要剪枝，即在已经不可能达到最终结果的时候提前退出递归。

这一题如果选取的元素已经大于$m$个了，就不可能正好选$m$个了，就需要退出。同理，如果所选元素的个数加上剩下的所有元素也达不到$m$，也需要退出。

如果把上一题的代码直接搬过来，加上剪枝，就是：

运行会发现结果是倒序的，大的结果在前面

xxxxxxxxxx
3 4 5 
2 4 5
2 3 5
2 3 4
1 4 5
1 3 5
1 3 4
1 2 5
1 2 4
1 2 3

这是由 我们先不选第$x$个元素再选第$x$个元素 造成的。

xxxxxxxxxx
calu(x+1);
v.push_back(x);
calu(x+1);
v.pop_back();

而第$x$个元素是比较小的（从小到大递归），本来应该在前面才对。

所以我们只需要调整一下push和pop的顺序即可。

xxxxxxxxxx
v.push_back(x);
calu(x+1);
v.pop_back();
calu(x+1);

总的就为：