洛谷-P1706 全排列问题（DFS）

目录

题目链接：

思路：

代码：

题目链接：

P1706 全排列问题 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

思路：

      如果n比较小，可以写n个for循环输出全排列。但是这种简单方法只能用于较小的n，如果n比较大，这种方法的代码非常冗长、难看。
  DFS非常适合实现全排列，代码清晰、简洁、优美。下面的C++代码能从小到大打印排列。

源自罗老师的博客：＜蓝桥杯软件赛＞零基础备赛20周--第12周--DFS基础（必考）-CSDN博客

可以画二叉树来帮助理解。

代码：

#include<bits/stdc++.h>
using namespace std;
int n;
int vis[10];    // 访问标记
int a[10];      //需要做全排列的数组
int b[10];      //当前DFS得到的全排列
void dfs(int step) {
    if (step == n+1) {     //已经对n个数做了全排列，输出全排列
        for (int i=1; i<=n; i++){
        	  printf("%5d",b[i]);
		}
        printf("\n");   //调试了才知道为什么这么写输出三个数字后换行，退出，然后进入下面那个遍历a[i]的for循环中
        return;            //结束，不再继续DFS
    }
    for (int i = 1; i <= n; i++) {    //遍历每个a[i]，放进全排列中
        if (vis[i] == 0) {   // 数字a[i]不在前面得到的排列中
            b[step] = a[i];  // 把a[i]放进排列
            vis[i] = 1;      // 保存现场：a[i]不能在后面继续用
            dfs(step+1);     // 继续把后面的数放进排列
            vis[i] = 0;      // 恢复现场：a[i]重新可以使用
        }
    }
    return;
}
int main() {
    cin >> n;
    for (int i=1; i<=n; i++)  a[i]=i;   //赋值得到n个数
    dfs(1);  //对a[1]~a[n]做全排列
    return 0;
}

 输出部分排列

  上述代码是打印n个数的全排列，如果需要打印n个数中任意m个数的排列，略作修改即可。例如n=4，m=3，修改C++代码这两处：第8行把step=n+1改为step=m+1，第9行i<=n改为i<=m。

 源自罗老师的博客：＜蓝桥杯软件赛＞零基础备赛20周--第12周--DFS基础（必考）-CSDN博客

多调试，了解计算机走的每一步。