CH0301 递归实现指数型枚举

Description

从这 n个整数中随机选取任意多个，输出所有可能的选择方案。

Input

一个整数 n。

Output

每行一种方案。同一行内的数必须升序排列，相邻两个数用恰好 1 个空格隔开。对于没有选任何数的方案，输出空行。本题有自定义校验器（SPJ），各行（不同方案）之间的顺序任意。

Sample Input

Sample Output

Limit

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

Analysis

这道题没什么特别的，递归就好。不过在动手之前可以分析一下时间复杂度：
若是求规模为的全排列，DFS 的时间复杂度为，本题规模为，即，大概需要运行的样子。不过本题要求「同一行内的数必须升序排列」，所以本题不需要枚举排列。

把中的每个数都看作一次独立选择：选它或不选它，每个数都分别有 2 种可能。对个数依次做出选择，根据乘法原理，所有选择组合数是

$个$

而每个子集都会进入一次 DFS，共次，即如果不考虑输出的话，时间复杂度为；考虑输出的话，集合最大为，所以代码实现的总的时间复杂度为。在的规模下大概是 1048576，大概能在以内完成，符合题目限制。

Solve

#include <iostream>

const int N = 25;

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

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

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

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

Loading...