全排列—dfs（递归算法）

1.class="superseo">dfs全排列深度优先算法思路导图

 此图来自AC中的Hasity作者，万分感谢；

2.dfs递归思想

• dfs就是一条路走到头，当无法再往下走时就往上退一步，再看有没有路可以走，如果还没有路的话就再回退一步，重复这个步骤，直到找到可以走的道路；
• 递归的主要思想在于不断调用本身的函数，层层深入，直到遇到递归终止条件后层层回溯，其思想与dfs基本吻合，从而调用递归实现dfs；
• 正如y总讲到的回溯，它是在计算机底层执行的（系统有一个隐藏的栈帮我们做回溯），我们无法看到，也不需要 *** 作。
  

  
  

  因此，理解并完成递归是它的一个难点;

• 时间复杂度为 O(n*n!)；空间复杂度为 O(n)；

3.主旨展现

• 用 a数组保存排列，当排列的长度为 n 时，是一种方案，进行输出；
• 用bool数组b表示数字是否用过。
  

  
  

  当b[i]为1时，i已经被用过，b[i] 为0时，i 没有被用过；

• dfs(i) 表示的含义是：在 a[i] 处填写数字，然后递归到下一个位置填写数字。
  

  
  

• 回溯：第 i 个位置填写某个数字的所有情况都遍历后， 第 i 个位置填写下一个数字。
  

  
  

4.例题（1）来喽

给定一个整数 nn，将数字 1∼n1∼n 排成一排，将会有很多种排列方法。

现在，请你按照字典序将所有的排列方法输出。

输入格式

共一行，包含一个整数 nn。

输出格式

按字典序输出所有排列方案，每个方案占一行。

数据范围

1≤n≤71≤n≤7

输入样例：

3

输出样例：

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

#include

using namespace std;

const int N=20;
int a[N],m;
bool b[N];

void dfs(int x)
{
    if(x==m)
    {
        for(int i=0; im;
    dfs(0);
    return 0;
}

5.例题（2）来喽

题目描述

二师兄一个寒假尽在吃喝玩乐，还老爱坑三师兄，于是乎，出了一个全排列的题目。

。

为了德玛西亚战斗吧~！~，。

纳尼~！~什么是全排列，，看下数据就懂啦，题目略难。

。

输入

一个m代表多少组数据，

每行一个9以内的数字n，输出1~n的全排列

输出

输出1~n的全排列每组数据之间有一个空行。

。

样例输入

3
1
2
3

样例输出

1

12
21

123
132
213
231
312
321

/*这里很多人会时间超限，原因在于cin和，cout；
  因为本身递归就是暴力算法，时间复杂度比较高，
  而cin,cout的编译时间是scanf,printf的3~4倍
  因此可能在这里被卡住；
*/
#include

using namespace std;

const int N=111;
int m,n,a[N],b[N];

void dfs(int x)
{
    if(x==n)
    {
        for(int i=0; i

欢迎分享，转载请注明来源：内存溢出

原文地址: http://outofmemory.cn/langs/577875.html