题解 | #递归实现组合型枚举#

实现比较简单，主要复习一下剪枝的方法：

1. 优先搜索结果小的分支

2. 排除等效冗余

3. 可行性剪枝

4. 最优剪枝

5. 记忆化DP

这里基本就是一个暴力搜索的问题，只能用到可行性剪枝。

#include <iostream>
#include <vector>

using namespace std;
const int N = 30;

int n,m;
int path[N];

void dfs(int u,int idx) {
    if(n - idx + u + 1 < m) return;
    if(u == m) {
        for(int i = 0;i < m;i++) cout << path[i] << ' ';
        cout << endl;
        return;
    }
    for(int i = idx;i <= n;i++) {
        path[u] = i;
        dfs(u + 1,i + 1);
        path[u] = 0;
    }
}


int main(){
//     freopen("input.txt","r",stdin);
    cin >> n >> m;
    dfs(0,1);
    return 0;    
}