[AcWing]842. 全排列数字

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

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

输入格式

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

输出格式

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

数据范围

1 < n < 7

输入样例：

1
3

输出样例：

1
2
3
4
5
6
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

算法思想

此题，适合用来理解DFS。DFS可以用树模型来理解。

image-20240419202755100

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <iostream>

using namespace std;

const int N = 10;

// 从1开始全排列的数字长度
int n;
// 数字是否被用过了
bool st[N];
// 值
int path[N];

// 关于数字1的全排列
void dfs(int u){
    // 数字u 为 n + 1说明 1~n 已经进行全排列了，此时直接输出
    if(u > n){
        for(int i = 1; i <= n; i++){
            cout << path[i] << " ";
        }
        cout << endl;
    }else{
        // 进行全排列
        for(int i = 1; i <= n; i++){
            // 如果这个数字还没用过
            if(!st[i]){
                // 就用一下这个数字
                st[i] = true;
                path[u] = i;
                // u + 1 数字的全排列
                dfs(u + 1);
                // 恢复现场
                st[i] = false;
            }
        }
    }
}

int main(){
    
    cin >> n;
    
    // 使用的path空间下标1开始，同时也是从1开始全排列
    dfs(1);
    
    return 0;
}