一、什么是深度优先搜索？
深度优先搜索就是说：从一个顶点开始，沿着某条路往下走，一直走到底，如果走完后发现不能达到目标解，就回溯，返回到上一个节点，换条路，然后继续走到底，如此往复，直至所有可能的结果都被搜索完。
通俗理解就是不撞南墙不回头这种感觉
二、深度优先搜索的特点
一般找不到最优解
当深度限制不合理时,可能找不到解,可以将算法改为可变深度限制
如果有解，且深度限制合理，就可以找到解
三、深度优先搜索适合解决什么问题？
给了某些初始条件，寻找是否有解，不要求最优解
四、全排列问题来详解DFS
全排列问题是，给一组数据，找出所有可能的组合
下面用1 2 3这三个数来举例子
我们现在相当于要往上面第一个状态里全排列填入1 2 3三个数字
最初三个空位都是空的，在第一个状态
在第一个状态的第一个空位填入1，到达第二个状态
在第一个状态的第二个空位填入2，到达第三个状态
在第一个状态的第三个空位填入3，到达第四个状态，空位填完，无法继续填数，输出这个解123
后退一步，退到第三个状态，第三个空位没有填，这个空位除了可以填3没有可以填的了，所以继续后退，退到第二个状态
在第二个状态的第二个空位填3，到达第五个状态
在第五个状态的第三个空位填2，到达第六个状态，空位填完，无法继续填数，输出这个解132
后退一步，退到第五个状态，第三个空位没有填，这个空位除了可以填2没有可以填的了，所以继续后退，退到第二个状态
在第二个状态的第二个空位除了填2和填3没有可以填的了，所以退到第一个状态
在第一个状态的第一个空位填入2，到达第七个状态
在第一个状态的第二个空位填入1，到达第八个状态
在第一个状态的第三个空位填入3，到达第九个状态，空位填完，无法继续填数，输出这个解213
后退一步，退到第八个状态，第三个空位没有填，这个空位除了可以填3没有可以填的了，所以继续后退，退到第二七个状态
在第七个状态的第二个空位填3，到达第十个状态
在第十个状态的第三个空位填1，到达第十一个状态，空位填完，无法继续填数，输出这个解231
后退一步，退到第十个状态，第三个空位没有填，这个空位除了可以填1没有可以填的了，所以继续后退，退到第七个状态
在第七个状态的第二个空位除了填1和填3没有可以填的了，所以退到第一个状态
在第一个状态的第一个空位填入3，到达第十二个状态
在第一个状态的第二个空位填入1，到达第十三个状态
在第一个状态的第三个空位填入2，到达第十四个状态，空位填完，无法继续填数，输出这个解312
后退一步，退到第十三个状态，第三个空位没有填，这个空位除了可以填2没有可以填的了，所以继续后退，退到第十二个状态
在第十二个状态的第二个空位填2，到达第十五个状态
在十第五个状态的第三个空位填1，到达第十六个状态，空位填完，无法继续填数，输出这个解321
后退一步，退到第十五个状态，第三个空位没有填，这个空位除了可以填1没有可以填的了，所以继续后退，退到第十二个状态
在第十二个状态的第二个空位除了填1和填2没有可以填的了，所以退到第一个状态，第一个状态的第一个空位除了填1和填2和填3没有可以填的了，故结束。
这个过程可以用下面的代码来表示：
#include <iostream>
using namespace std;
const int N = 20;
int n;
int a[N]; //结果数组
bool s[N];//节点状态
void dfs(int x){// x 是递归层数，深搜层数
if(x == n){//如果已经到最后一层
for(int i=0;i<n;i++){//打印结果
cout << a[i] << " ";
}
cout << endl;
return ;
}
else {
for(int i=1;i<=n;i++){//将在每一层上可能出现的所有的数都遍历一次
if(!s[i]){
a[x] = i;//存储这一层的值
s[i] = true;//将i这个数的状态改为true，表示已经访问过，这样在下面的dfs(x+1)中会从i+1这个点开始
dfs(x+1);//递归进入下一层
s[i] = false;// 恢复现场,便于回溯
}
}
}
}
int main(){
cin >> n;
dfs(0);
return 0;
}
