[dfs入门]全排列问题

· · 个人记录

first：题目

描述

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

输入

输入一个数字n(1≤n≤9)

输出

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

second：分析

直接递归即可。

设dep代表枚举的深度，即第dep个数应该放什么，再一一枚举，如果这个数没有用到，则使用，然后枚举下一层，结束后再枚举下一个数。

当全部枚举完后，即dep=n+1时，输出，时间复杂度为O(n\ !)

third：新知

我们可以开一个bool数组来判断是否枚举，如果为false则没有，反之，true则有。

枚举时，我们先判断有没有用，如果没有用过，就加入，并且这个数变成true，递归下一层。

当这个数递归完以后，再把这个数变成true，继续枚举，这叫做回溯法。

fourth：注意

1、为了不重复，要设数组表示状态。

2、及时回溯，以便下次搜索。

3、当搜到第n+1次时，代表全部搜好了，然后输出。

fifth：代码

#include<bits/stdc++.h>
using namespace std;
int n;
int a[101];
bool node[101];
void write()
{
    for(int i=1;i<=n;i++)
    {
        cout<<a[i]<<" ";
    }
    cout<<endl;//输出
}
void dfs(int dep)
{
    if(dep==n+1)//搜索完了
    {
        write();
        return;
    }
    for(int i=1;i<=n;i++)
    {
        if(node[i]==false)//没有用过
        {
            a[dep]=i;
            node[i]=true;//使用
            dfs(dep+1);//下一个数
            node[i]=false;//回溯
        }
    }
}
int main()
{
    cin>>n;
    dfs(1);//从第一层开始
    return 0;
}