题目描述

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

dfs

python 代码

def dfs(u):         #u表示当前枚举到第几位
    if u == n:
        for i in range(n):
            print(path[i],end=' ')
        print()
        return
    for i in range(1,n+1):
        if st[i]==False:
            path[u] = i
            st[i] = True
            dfs(u+1)            #递归到下一层
            #path[u] = 0        回溯，path[u]会在上一步赋值，所以这一步可省略
            st[i] = False       #回溯


if __name__ == "__main__":
    n=int(input())
    path = [0]*(n+5)
    st = [False] * (n+5)
    dfs(0)

C++ 代码

#include <iostream>
using namespace std;

const int N=10;
int n;
int path[N];
bool st[N];

void dfs(int u){
    if (n==u){
        for(int i=0;i<n;i++) printf("%d ",path[i]);
        puts("");
        return;
    }

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

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