题目描述

给定一个整数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

算法1

STL next_permutation函数

C++ 代码

#include<stdio.h>
#include<algorithm>
using namespace std;
int n,a[1000];

int main(){
    scanf("%d",&n);
    for(int i = 0;i < n;i++)
    {
        a[i]=i + 1;
    }
    do
    {
        for(int i = 0;i < n;i++) 
        printf("%d ",a[i]);
        puts("");
    }while(next_permutation(a,a+n));

    return 0;
}

算法2

DFS

C++ 代码

#include <iostream>
using namespace std;
const int N = 10;
int n;
//深度优先搜索，参数比较复杂
void dfs(int u, int nums[], bool st[])  //u表示当前枚举到第几位
{
    if (u > n) 
    {
        for (int i = 1; i <= n; i ++ ) printf("%d ", nums[i]);
        puts("");
    }
    else
    {
        for (int i = 1; i <= n; i ++ )
            if (!st[i])
            {
                st[i] = true;
                nums[u] = i;
                dfs(u + 1, nums, st);
                st[i] = false;  // 恢复现场
                                // 返回上一层数的时候相当于st为0，没用过
            }
    }
}

int main()
{
    scanf("%d", &n);

    int nums[N];  //当前每个位置填的数
    bool st[N] = {0}; //每个数有没有被用过，一开始都设成没用过

    dfs(1, nums, st);

    return 0;
}