【普及−】洛谷P1706 全排列问题

见：P1706 全排列问题 - 洛谷

题目描述

按照字典序输出自然数 1 到 n 所有不重复的排列，即 n 的全排列，要求所产生的任一数字序列中不允许出现重复的数字。

输入格式

一个整数 n。

输出格式

由 1∼n 组成的所有不重复的数字序列，每行一个序列。

每个数字保留 5 个场宽。

输入输出样例

输入 #1

3

输出 #1

    1    2    31    3    22    1    32    3    13    1    23    2    1

说明/提示

1≤n≤9。

算法解析

DFS，

对楼上的回溯+剪枝进行详解。

我们以N=3为例，

构造一棵搜索树（或说是状态树）来进行搜索。

同时构造出三个格子，

用来存放搜索树中的结果。

现在，我们从第一格开始搜索。

第一格填1的搜索树如下：

所以N=3的情况下，

第一格填1的排列情况共有两种123,132.

第一格填2的搜索树如下：

所以N=3的情况下，

第一格填2的排列情况共有两种 213,231.

如果你看懂了，

请你自己画画第一格填3的搜索树。

程序实现

我们总结一下在上一部分中的思路在程序中如何实现。

先定义两个数组，

一个是用来存放解的，

一个是用来标记该数是否用过。

接下来就是写深搜的函数了。

主要思路：

先判断格子是否填满了，

如果填满，

则print()一下。

如果没有填满，

则开始循环，

在循环中先判断当前填的数是否用过，

如果没有，

则填入，

搜索下一格。

程序实现如下：

#include <bits/stdc++.h>
using namespace std;
#define int long long//十年OI一场空，不开long long见祖宗
const int maxn=10;
int a[maxn];
int t[maxn];
int n;void dfs(int k){if(k==n+1){for(int i=1;i<=n;i++){cout<<"    "<<a[i];}cout<<endl;return;}for(int i=1;i<=n;i++){if(t[i]==0){a[k]=i;t[i]=1;dfs(k+1);t[i]=0;}		}return;
}signed main() {	cin>>n;dfs(1);return 0;
}

三连一下吧

欢迎评论