dfs专题 P1706 全排列问题——洛谷（题解）

题目描述

按照字典序输出自然数 11 到 �n 所有不重复的排列，即 �n 的全排列，要求所产生的任一数字序列中不允许出现重复的数字。

输入格式

一个整数 �n。

输出格式

由 1∼�1∼n 组成的所有不重复的数字序列，每行一个序列。

每个数字保留 55 个场宽。

输入输出样例

输入 #1复制

3

输出 #1复制

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

说明/提示

1≤�≤91≤n≤9。

想法：

位置枚举，第一个位置有n种选择，第二个位置有n-1种……

代码：

#include<bits/stdc++.h>
using namespace std;
int n;
int pl[10];//排列 
int st[10];//有无被选过 
void dfs(int wz){
    if(wz>n){
        for(int i=1;i<=n;i++)
            printf("%5d",pl[i]);
        printf("\n");
        return ;
    }
    for(int i=1;i<=n;i++){
        if(st[i]) continue;//选过了 
        pl[wz]=i;//某个位置放i 
        st[i]=1;
        dfs(wz+1);
        st[i]=0; 
    }
}
int main(){
    cin>>n;
    dfs(1);
}