题目描述

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

输入格式

输入一个整数 n。

输出格式

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

解题思路

看到这种排列的题目，我们第一时间想到的就是dfs，通过层数u来控制层数
但是不太一样的是之前是给定了按照一定数量来排序，然而这里是从1位开始排的。。
所以使用if-else语句中else进行递归，增加排列的位数直到n位。
然后注意的是从1开始深度搜索：
如果是dfs(0)，实际上是从 book[0] 开始进行搜索。由于 book 数组是一个布尔类型的数组，默认值为 false，所以在第一次递归调用 dfs 时，book[0] 会被设为 true，然后会调用 dfs(1) 来继续搜索。这就会导致结果输出两次，因为在 dfs(1) 中会再次搜索到相同的结果。
还有就是为什么是u==n+1？
在递归的时候当到n+1才完整的遍历完前n个，从第n个向前回溯输出正确答案

见AcWing 823. 排列(深度搜索)

C++ 代码

#include<bits/stdc++.h> //万能头

using namespace std;    //描述空间

int n;                  //全局变量个数
bool book[1005];        //开一个布尔判断数组

void dfs(int u){        //定义深度搜索函数
    if(u==n+1){         //如果到n+1项（实际遍历完n个）
        for(int i=1;i<=n;i++){  //回溯并且输出答案
            if(book[i]){
                cout<<i<<" ";
            }
        }
        cout<<endl;     //记得有一个没有的情况
        return;         //回溯
    }else{              //这段else语句的作用就是形成深度搜索树杈
        book[u]=true;   //树杈1：如果调用了u
        dfs(u+1);       
        book[u]=false;  //树杈2：如果没有调用u
        dfs(u+1);
    }
}
int main(){             //主函数
    cin>>n;             //用户输入n
    dfs(1);             //从dfs（1）开始
    return 0;           //返回值
}

篇章

上一篇：语法基础课总结
https://www.acwing.com/file_system/file/content/whole/index/content/10493095/
下一篇：AcWing 94. 递归实现排列型枚举
https://www.acwing.com/solution/content/217237/