算法模板：全排列数字

文章目录

题目链接：

  • https://www.acwing.com/problem/content/844/

给定一个整数 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. 初始化/创建path[]和st[]数组，path数组记录已经选择的数字排列形式，st数组记录以及选择的数字st[i]=1;表名i已经放入path数组中；
  2. dfs函数传入u参数，如果u==n为真，就遍历path输出全部元素；
  3. 如果u==n为假，则在循环判断1-n中还有那个是没有放入，则按顺序放入path数组，放入后st[i]=true；
  4. 将u+1传入dfs实现递归，再重复2-3步骤；
  5. 回溯的时候要还原现场，st[i]=false;

CODE:

#include<iostream>
using namespace std;
const int N=10;
int path[N];
bool st[N];
int n;
void dfs(int u){
    if(u==n){
        for(int i=0;i<n;i++)printf("%d ",path[i]);
        printf("\n");
        return;
    }
    for(int i=1;i<=n;i++){
        if(!st[i]){
            path[u]=i;
            st[i]=true;
            dfs(u+1);
            st[i]=false;
        }
    }
}
int main(){
    scanf("%d",&n);
    dfs(0); 
    return 0;
}

}
}
int main(){
scanf("%d",&n);
dfs(0);
return 0;
}