洛谷P1706 全排列问题

题目描述

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

输入输出格式

输入格式：

n(1≤n≤9)

输出格式：

由1～n组成的所有不重复的数字序列，每行一个序列。每个数字保留5个常宽。

输入输出样例

输入样例#1： 复制

3

输出样例#1： 复制

    1    2    3

    1    3    2

    2    1    3

    2    3    1

    3    1    2

    3    2    1

深搜的入门题。
为什么放在了我的博客上？
因为本弱正在重温深搜，最后发现自己啥也不是。于是开始重刷基础题，顺便也对深搜有了更扎实一点点的理解。在这里分享给像我一样的新手菜鸟们。
任意一本算法书都会告诉你顾名思义，事实上深搜和广搜的确就是顾名思义，一个先往深了走，一个先往广了走，一个按链，一个按层。
但是我做深搜的时候会遇到很多困扰：
这题为什么就用深搜了？
这题的深搜代码为啥这么写？
这题的图呢？
是的，最终要点就是：树呢？图呢？
所以，针对每个深搜问题，我们都需要先构建搜索树。
然后在树上搜索，就解决了我刚刚的问题。
而以后学深搜，对剪枝方面的理解，也会更加深刻。

比如这道题，以N=3为例，一共有3个空位。
第一位分别放1，2，3。
假如第一位是1（深搜嘛）
第二位也可以放1，2，3
放1不行（剪枝）
然后第三位可以放1，2，3
在第二位分别是2，3的基础上分别剪枝。
思路就出来了。

接下来是搜素函数。
搜索函数是深搜中的极其重要的一个环节。
这道题要建两个数组。
第一个存数字。
第二个存标记。
然后要注意递归边界。
如果搜满了就输出。
如果没搜满就开始搜，先填一个格子，标记，填下一个，再深搜。
代码如下：

#include<cstdio>

using namespace std;

int n;

int a[],v[];

void dfs(int x)

{

    if(x==n+)

    {

        for(int i=;i<=n;i++)

            printf("    %d",a[i]);

        printf("\n");

        return;

    }

    for(int i=;i<=n;i++)

    {

        if(v[i]==)

        {

            a[x]=i;

            v[i]=;

            dfs(x+);

            v[i]=;

        }

    }

}

int main()

{

    scanf("%d",&n);

    dfs();

    return ;

}