本文主要是介绍温故知新：dfs-842. 排列数字，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
给定一个整数 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
| 难度：简单 |
| 时/空限制：1s / 64MB |
| 总通过数：96065 |
| 总尝试数：121392 |
| 来源：模板题 |
| 算法标签 |
思路
没有想到几天之前非常熟练的模板题现在忘得差不多了，看来之前写过的题目需要复习一下hh
1.深度优先搜索：达到我们需要的要求，也就是说走到终点，我们就输出答案
if(u>n){for(int i=1;i<=n;i++) printf("%d ",g[i]);printf("\n");return;}2.判断每一次搜索每一个数字的状态，我们不能使用已经使用过的数字
for(int i=1;i<=n;i++){if(!state[i]){state[i]=true;g[u]=i;dfs(u+1);state[i]=false;g[u]=0;}}并且循环需要从1开始使用，因为我们使用的数字是从1开始使用的
先修改数字的状态，然后把相应的数字存到我们需要输出的路径数组里面，然后递归调用函数本身，然后恢复现场，把原来的状态恢复
3.代码细节是输出的时候下标是i，刚刚手残写成了g[N]，输出很大的数字，非常奇怪的bug
for(int i=1;i<=n;i++) printf("%d ",g[i]);4.万能头文件在acwing上运行时间（这道题目） 是9ms,iostream是11ms，是啥情况
代码
#include<iostream>
using namespace std;int n;
const int N=10;
int g[N];
bool state[N];void dfs(int u)
{if(u>n){for(int i=1;i<=n;i++) printf("%d ",g[i]);printf("\n");return;}for(int i=1;i<=n;i++){if(!state[i]){state[i]=true;g[u]=i;dfs(u+1);state[i]=false;g[u]=0;}}
}int main()
{scanf("%d",&n);dfs(1);return 0;
}
这篇关于温故知新：dfs-842. 排列数字的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
