[数据结构与算法]递归实现排列型枚举

本题是一道递归的经典题目，初学者学习递归时可能觉得难以理解，我们可以手画递归搜索树将每种情况遍历出来，然后捋清思路后用代码来实现。

有图可知先从根节点开始遍历，当n为3时有3种情况，分别为1，2，3，然后看1的子树，后面两位未确定有两种可能性，左子树填2，剩下一位只能填3，其他遍历思想上同。接下来我们用代码来实现。

#include<bits/stdc++.h>

using namespace std;

const int N=10;
int n;
bool st[N];    //判断数是否被记录
int path[N];   //记录递归搜索树的路径内容

void dfs(int u)
{
    if(u>n)
    {
        for(int i=1;i<=n;i++)
        {
            cout<<path[i]<<" ";

        }  cout<<endl;

    }
    else
    {
        for(int i=1;i<=n;i++)
        {
            if(!st[i])    //当前这一位没有被用过的话
            {
                path[u]=i;        //将i填进去
                st[i]=true;       //标记i
                dfs(u+1);   //递归到下一层
                st[i]=false;      //恢复现场
                path[u]=0;
            }
        }
    }
}
int main()
{
    scanf("%d",&n);
    dfs(1);    //从1开始遍历
    return 0;
}

问题得到解决。