题目链接

AcWing 92. 递归实现指数型枚举

引用

看了大佬的题解之后才发现这题还能这么玩???

秦淮岸灯火阑珊 AcWing 92. 递归实现指数型枚举

lovebecky AcWing 92. 递归实现指数型枚举

shizhengLee AcWing 92. 详细注释y总代码。

题目描述

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

样例

输入格式

输入一个整数 n。

输出格式

每行输出一种方案。

同一行内的数必须升序排列,相邻两个数用恰好 1 个空格隔开。

对于没有选任何数的方案,输出空行。

本题有自定义校验器(SPJ),各行(不同方案)之间的顺序任意。

数据范围

$1 \leq n \leq 15$

输入样例:

3

输出样例:


3
2
2 3
1
1 3
1 2
1 2 3

算法

(递归) $O(2^n)$

从题目的意思中可以看出,这是要我们列出 $1$ ~ $n$ 中所有数字可能出现的组合情况。

有关与递归的题都可以画一颗递归搜索树,具体的可以看下图

一共有 $1$ ~ $n$ 个数,每一个数都有选与不选两种结果,故所有的方案数为 $2^n$ 个。这也是为什么叫指数型枚举的原因

接着就是如果使用递归进行枚举了,首先用一个数组来存储数字的选中状态,再用一个变量 u 来记录枚举到第几个数了。

但是不可能说有 $2^n$ 种方案就要定义那么多个数组与变量,这两个都是可以循环利用的,那么怎么利用呢?

递归的性质已经很明白的说明了,递归到底层(终止条件)的时候是会有一个回溯的过程,那么在这个过程中只要把数组对应元素的值还原就行了(当然因为并不需要用到数组的值来进行判断等操作,是直接赋值的,所以恢复现场这一操作不是必须的,但因为是初学,所以加上去可以更好的理解递归的性质)

递归实现指数型枚举

时间复杂度 $O(2^n)$

每一个位置都只有两种结果,n个就是 $2^n$

C++ 代码

#include <iostream>

using namespace std;

const int N = 25;

int n;
int st[N];

void dfs(int u) {
    
    // 选够数字之后进行判断对应方案数的输出情况
    if(u > n) {
        for(int i = 1; i <= n; i ++)
            if(st[i] == 1) cout << i << " ";
        cout << endl;
        
        return;
    }
    
    // 1选 2不选
    st[u] = 1;
    dfs(u + 1);
    // 恢复现场
    st[u] = 0;
    
    st[u] = 2;
    dfs(u + 1);
    // 恢复现场
    st[u] = 0;
}

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

Q.E.D.


都懂一点,不是很懂的小捞仔