0842

842. 排列数字

题目

给定一个整数 $n$，将数字 $1 \sim n$ 排成一排，将会有很多种排列方法。

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

输入格式

共一行，包含一个整数 $n$。

输出格式

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

数据范围

$1 \le n \le 7$

输入样例：

3

输出样例：

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

题解

前置题目：0000

前置知识：递归

本题知识：搜索与图论-DFS

题目分析

使用dfs，过程如下

                              _ _ _
                   /            |            \
              1 _ _           2 _ _          3 _ _
               /  \            /   \          /   \
           1 2 _  1 3 _     2 1 _  2 3 _   3 1 _  3 2 _
             |      |         |      |       |      |
           1 2 3  1 3 2     2 1 3  2 3 1   3 1 2  3 2 1

核心点是保存现场和回溯

• 用一个数组保存当前的路径
• 再用另一个数组保存已经使用过的数字
• 深度优先搜索到全部数字用完后，即完成一个排列方案
• 然后回到上一个状态，直到所有方案都枚举过了