题目描述

排列数字（DFS）

dfs以树状来进行所有数字的存储和搜索（深度优先遍历）（竖着搜索）

根节点的序号为0

每次完整的层遍历完后都要回溯，因此每用过一层都要使他恢复到原来的样子

C++ 代码

#include<iostream>
using namespace std;
const int N=10;
int n;            //dfs以一棵树得形式进行搜索，根节点为0，，下面几层分别为1、2...
int path[N];
bool st[N];   //默认为false

void dfs(int u)  //层号
{
    if(u==n)    //当相等时，意味着已经将所有层都搜索完
    {
        for(int i=0;i<n;i++)cout<<path[i]<<" ";   //所以按层依次输出
        puts("");
        return ;
    }

    for(int i=1;i<=n;i++)      //枚举所有数
    {
        if(!st[i])   //如果这个数没有被用过
        {
            path[u]=i;    //不断更新放入树中的数
            st[i]=true;   //标志该数被用过了
            dfs(u+1);     //这一层放好了数之后，dfs下一层       /////输出完了之后回溯
            st[i]=false;  //恢复原来的状态
        } 
    }
}
int main()
{
    cin>>n;

    dfs(0);   //从根节点开始

    return 0;
}