递归实现指数型枚举（递归）

た入场券 2022-11-30 12:44 178阅读 0赞

>  写在前面：大家好！我是`ACfun`,我的昵称来自两个单词`Accepted`和`fun`。我是一个热爱ACM的蒟蒻。这篇博客来详解一下递归实现指数型枚举。如果博客中有不足或者的错误的地方欢迎在评论区或者私信我指正，感谢大家的不吝赐教。我的唯一博客更新地址是：[https://ac-fun.blog.csdn.net/][https_ac-fun.blog.csdn.net]。非常感谢大家的支持。一起加油，冲鸭！  
>  `用知识改变命运，用知识成就未来！加油 (ง •̀o•́)ง (ง •̀o•́)ง`

### 文章目录 ###

*  题目信息
 *   *  题目描述
     *  输入格式
     *  输出格式
     *  数据范围
     *  输入样例
     *  输出样例
 *  题解
 *   *  解题思路
     *  解题代码

原题链接： [递归实现指数型枚举][Link 1]

# 题目信息 #

## 题目描述 ##

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

## 输入格式 ##

输入一个整数n。

## 输出格式 ##

每行输出一种方案。同一行内的数必须升序排列，相邻两个数用恰好1个空格隔开。对于没有选任何数的方案，输出空行。

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

## 数据范围 ##

> 1 ≤ n ≤ 15

## 输入样例 ##

## 输出样例 ##

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

# 题解 #

## 解题思路 ##

我们可以从 `1 ~ n` 依次考虑每个数选还是不选，我们可以以一个树的形式来描述选还是不选的情况。对于每一种情况有三种状态可以选择：`待考虑、选、不选`。我们以 `0` 表示待考虑，`1` 表示选该位，`2` 表示不选。比如当 `n = 3` 的时候，我们画出的递归搜索树如下：  
![递归树][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNTc1NTA3_size_16_color_FFFFFF_t_70]  
 这其实就是一个 `深度优先搜索` 的过程，我们先考虑第一位，第一位有两种情况：左子树为不选第一位的情况，右子树为选第一位的情况；当不选第一位时又分成了两种情况，即在不选第一位的情况下第二位不选的情况（左子树）和第二位选的情况（右子树）；然后又分成两种情况，选择第三位和不选择第三位。以上是整个左子树的分析情况，即刚开始第一位不选的情况。右子树第一位选择的情况下同理。

所以我们可以使用 `dfs` 来递归遍历所有的情况，首先递归遍历不选的情况，然后再递归遍历选择的情况。当每层递归到结束时依次遍历我们记录每个点的状态，如果是 `1` 我们就输出该数，否则就不输出该数。

## 解题代码 ##

#include<iostream>
    #include<cstdio>
    using namespace std;
    
    const int N = 15;
    
    int n;
    int s[N];  // 用来记录每个点的状态： 0 表示待考虑，1 表示选择该数， 2 表示不选
    
    void dfs(int x) { 
        if (x == n) { 
            for (int i = 0; i <= n; i++) { 
                if (s[i] == 1) { 
                    printf("%d ", i + 1);
                }
            }
            printf("\n");
            return;
        }
        
        s[x] = 2;
        dfs(x + 1);  // 第一个分支，不选
        s[x] = 0;    // 恢复现场
        
        s[x] = 1;
        dfs(x + 1);  // 第二个分支，选
        s[x] = 0;
    }
    
    int main() { 
        cin >> n;
        dfs(0); // 从第一个开始遍历
        return 0;
    }

--------------------

> 我是ACfun，感谢大家的支持！  
> ![冲鸭！][20200824123318925.png]

[https_ac-fun.blog.csdn.net]: https://ac-fun.blog.csdn.net/
[Link 1]: https://www.acwing.com/problem/content/94/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNTc1NTA3_size_16_color_FFFFFF_t_70]: /images/20221123/2af7951c5a0a4045add2a84554e01890.png
[20200824123318925.png]: /images/20221123/02971c56dfd24ceb8b4ee172b364ce47.png