AcWing | 【DFS】排列数字

题目内容

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

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

输入格式

共一行，包含一个整数n。

输出格式

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

数据范围

1≤n≤7

输入样例：

输出样例：

思路：

题目要求输出数组的全排列，核心是考虑清楚以什么样的顺序搜索最方便：
注意需要回溯，以保证下一次搜的时候是按最原始的时候搜的。

完整代码：

#include<iostream>
using namespace std;
const int N=10;
int n;
int path[N];//用来存路径
bool st[N];//用来存状态 是否被用过
void dfs(int u){
    if(u==n){//如果已经全部遍历完了 就直接输出路径即可，u相当于树的层数
        for(int i=0;i<n;i++)printf("%d ",path[i]);
        puts(" ");
        return;
    }
    for(int i=1;i<=n;i++){
        if(!st[i]){//如果i没被用过 就用一下他
            path[u]=i;//把路径记录下来
            st[i]=true;//修改状态表示已经被用过了
            dfs(u+1);//递归下一位
            st[i]=false;//回溯 恢复现场
        }
    }
}
int main(){
    cin>>n;
    dfs(0);
    return 0;
}