CH0302 递归实现组合型枚举

Description

从 1~n 这 n 个整数中随机选出 m 个，输出所有可能的选择方案。,,。

Input

两个整数 n，m。

Output

按照从小到大的顺序输出所有方案，每行 1 个。首先，同一行内的数升序排列，相邻两个数用一个空格隔开。其次，对于两个不同的行，对应下标的数一一比较，字典序较小的排在前面（例如 1 3 9 12 排在 1 3 10 11 前面）。

Sample Input

5 3

Sample Output

Limit

Time Limit	Memory Limit
1 秒（C/C++/Rust/Pascal），2 秒（其他语言）	32 M（C/C++/Rust/Pascal），64 M（其他语言）

Analysis

同 CH0301 递归实现指数型枚举，不过本题需要分析一下数据范围：
由题目条件,,：

再结合，对固定的，有

要让的取值区间非空，必须，再结合，得到。分段写出：

总之，若均为整数，数据范围可总结为：

其中最大为，最大也为（此时）。

Solve

#include <iostream>

const int N = 30;

int n, m, st[N];
int ans[N], idx;

void dfs(int p, int cnt) {
    if(cnt == m)
        for(int i = 0; i < idx; ++i)
            std::cout << ans[i] << ' ';

    if(cnt == m) std::cout << '\n';
    for(int i = p + 1; i <= n; ++i) {
        if(!st[i]) {
            st[i] = 1;
            ans[idx++] = i;
            dfs(i, cnt + 1);
            st[i] = 0;
            --idx;
        }
    }
}

int main () {
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);
    
    std::cin >> n >> m;
    for(int i = 1; i <= n; ++i)  {
        st[i] = 1;
        ans[idx++] = i;
        dfs(i, 1);
        st[i] = 0;
        --idx;
    }
}

时间复杂度依然为

Loading...