题目描述

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

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

样例

3

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

算法

(递归搜索树)

1. 唯一要注意的就是a[u]，表示当前枚举到了第u个坑。在第u个坑上放数字i，然后递归到下一层。成功了就输出。没有就回溯回来，恢复现场，第u个坑的数字重新填一个。

时间复杂度

$O(n!)$

C++ 代码

#include <iostream>

using namespace std;

const int N = 11;

int n;
int a[N];
bool st[N];

void dfs(int u)
{
    if(u == n)
    {
        for(int i = 0; i < n; i ++)
            cout << a[i] << ' ';
        cout << endl;
    }

    for(int i = 1; i <= n; i ++)
    {
        if(!st[i])
        {
            st[i] = true;
            a[u] = i;               // **1
            dfs(u + 1);
            st[i] = false;
        }
    }
}


int main()
{
    cin >> n;

    dfs(0);

    return 0;
}