题目描述

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

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

输入格式
共一行，包含一个整数n。

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

数据范围
1≤n≤9

样例

输入样例：

3

输出样例：

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

DFS

C++ 代码

#include <iostream>

using namespace std;

const int N = 10;

int n;
int p[N]; //用于记录当前方案wei
int x = 1 << 10; // 用于辅助DFS 维护方案记录时不出现重复的情况  当前方案中 1 ~ 9 排过的对应位为 1 反之为 0 

void dfs(int u) // dfs(u) 表示当前到第 u - 1 位
{
    if(u == n + 1) // 当排到第 n 位时 输出当前方案
    {
        for(int i = 1; i <= n; i ++) cout << p[i] << ' ';
        cout << endl;
        return ;
    }

    for(int i = 1; i <= n; i ++) // 自低到高位遍历 x 
        if(!(x >> i & 1)) // 若当前位对应数字 未排过 则:
        {
            x |= 1 << i; // 置1 
            p[u] = i; // 将当前位对应数字排入
            dfs(u + 1); // 搜索下一位上待排数字
            x &= ~(1 << i); // 排完一次后返回上一层置 0 换方案
        }

}

int main()
{
    cin >> n;
    dfs(1);
    return 0;

}