..
AcWing 93. 递归实现组合型枚举
我们只需要在指数型枚举的程序的 calc 函数开头添加以下这条语句即可。
if (chosen.size() > m || chosen.size() + (n - x + 1) < m) {
return;
}
这就是所谓的简直。
寻找变换路线其实就是 “搜索” 的过程。
如果能够及时确定当前问题一定是无解的，就不需要到达问题边界才返回结果。
在本题中，如果已经选择了超过 $m$ 个数，或者即使再选上剩余所有的书也不够 $m$ 个，就可以提前得知当前问题无解了。
这条剪枝保证我们一旦进入无解的分支就会立刻返回。
所以时间复杂度就从 $2^n$ 降低为 $C^m_n$。
完整代码：递归实现组合型枚举.cpp