题目链接

算法竞赛进阶指南-6.递归实现组合型枚举

从 ${1∼n}$ 这 ${n}$ 个整数中随机选出 ${m}$ 个，输出所有可能的选择方案 => 即${C_{n}^{m}}$

同一行内的数升序排列，相邻两个数用一个空格隔开

对于两个不同的行，对应下标的数一一比较，字典序较小的排在前面

Method : 递归

本题相较上一个题目，多一个(select == m)的条件。

其次，可以使用剪枝去优化时空复杂度，n + 1 - depth < m - select 是表示剩下的数量 < 要选的数量。

#include <vector>
#include <iostream>

using namespace std;

int n, m;
vector<int> choosen;

void dfs(int depth, int select) {
    // prune
    if (select > m || n + 1 - depth < m - select) {
        return;
    }
    
    // boundary
    if (select == m) {  
        for (int i = 0; i < choosen.size(); i ++) {
           	printf("%d ", choosen[i]);
        }
        cout << endl;
        return;
    }
    if (depth == n + 1) return;
        
    choosen.emplace_back(depth);
    dfs(depth + 1, select + 1);
    // recover
    choosen.pop_back();
    dfs(depth + 1, select);
}

int main() {
    cin >> n >> m;
    dfs(1, 0);
    return 0;
}

复杂度分析

• 时间复杂度${O(mlog_2n)}$， 其中$log_2n$为递归函数栈的深度。 但由于剪枝，实际时间复杂度会小于该理论时间复杂度。

• 空间复杂度${O(m)}$,数组${choosen}$的空间为${m}$，另外递归函数栈会花费额外常数级空间。