题目描述

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

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

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

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

数据范围
1≤n≤7

样例

输入样例：
3
输出样例：
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

算法1

(暴力深搜)

时间复杂度 $O(n^n)$

C++ 代码

#include<bits/stdc++.h>
using namespace std;

int n,a[10];//a[w]表示第w位上的数
bool b[10];

void DFS(int w)//表示做到第几位
{
    if(w==n+1)//做完了最后一位
    {
    for(int i=1;i<=n;i++) for(int j=1;j<i;j++) if(a[i]==a[j]) return;//有重复不满足题意
        for(int i=1;i<=n;i++) printf("%d ",a[i]);//输出这种情况
        printf("\n");
        return;
    }
    for(int i=1;i<=n;i++)//还有数没用
    {
        b[i]=false;
        a[w]=i;
        DFS(w+1);
        b[i]=true;//前w位已经确定且第w位为i的情况已经考虑完了，第w位没用i，i可以继续使用。
    }
}


int main()
{
    memset(b,true,sizeof(b));//初始化 
    scanf("%d",&n);
    DFS(1);//w从第一位开始做
}

算法2

(深搜+剪枝)

时间复杂度 $O(n!)$

C++ 代码

#include<bits/stdc++.h>
using namespace std;

int n,a[10];//a[w]表示第w位上的数
bool b[10];

void DFS(int w)//表示做到第几位
{
    if(w==n+1)//做完了最后一位
    {
        for(int i=1;i<=n;i++) printf("%d ",a[i]);//输出这种情况
        printf("\n");
        return;
    }
    for(int i=1;i<=n;i++)//还有数没用
    {
        if(b[i]==false) return;剪枝：若以前用过i且现在也用i，与题目矛盾
        b[i]=false;
        a[w]=i;
        DFS(w+1);
        b[i]=true;//前w位已经确定且第w位为i的情况已经考虑完了，第w位没用i，i可以继续使用。
    }
}


int main()
{
    memset(b,true,sizeof(b));//初始化 
    scanf("%d",&n);
    DFS(1);//w从第一位开始做
}