一、全排列问题
问题简述
问题求解
列出所有从数字1到数字n的连续自然数的排列，要求所产生的人一数字序列中不允许出现重复的数字。
输入格式
一个正整数N（N<=20）
输出格式
若干行，由1-n组成的所有不重复的数字排列，每行一个序列。要求按照样例的所示的按字典序输出输出。
Sample Input
3
Sample Output
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1思路1：
这个问题有多个解，其中每个解都包含n个数字，如果n是确定的，则可以通过n层for循从小到大环枚举每个元素的值进行求解！（因为题目要求按字典序从小到大输出）
如：N=3：
for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { for(int k=1;k<=n;k++) { if(i!=j && i!=k && j!=k) { cout<<i<<' '<<j<<' '<<k<<endl; } } } }复杂度：O(
)
算法漏洞1：
时间复杂度太高！超时！
算法漏洞2：
无法事先知道n的大小，所以不能知道要写几层for循环，此算法不可行！
尝试解决：
算法漏洞2可以解决，可以尝试写一个递归程序执行n次递归。
算法漏洞1无法此算法下无法解决，因为我们的思路是枚举方案中的每一个数，必定少不了n层循环！
结论：此算法不可行！
思路2：
搜索！当n不确定时，解中 元素数量也不确定，导致无法确定for循环的层数，可以使用递归模拟层次。
?这种穷举一个问题解空间中所有的可能情况，从而求出问题的解的一种方法称为搜索。
n个元素的全排列，使用搜索算法，总共会生成
画一个搜索树：
?搜索过程中如果发现某个解肯定不是有效解，则可以停止对当前解的搜索，降低搜索量!
二、回溯法
回溯法是一种优搜索法，按深度优先策略，从根节点出发搜索解空间树。算法搜索至解空
间树的任一节点时，先判断该节点是否包含问题的解，如果肯定不包含，则跳过对该节点
为根的子树的搜索（剪枝）；否则进入该子树，继续按深度优先策略搜索，如果发现原先
选择并不优或达不到目标，就退回一步重新选择。
所谓问题的解空间，即问题所有的解的集合。
回溯法在求解过程中不保留完整的搜索结果，而搜索则记下完整的搜索结果。
回溯法步骤：
① 定义问题的解和解空间，问题的解空间至少应包含问题的一个解。
② 确定结点的扩展搜索规则。
③ 以深度优先搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。
三、例题
N皇后问题
题目描述
魔法世界历史上曾经出现过一个伟大的罗马共和时期，出于权力平衡的目的，当时的政治理论家波利比奥斯指出：“事涉每个人的权利，绝不应该让任何权力大到压过其他力量，使他人无法立足于平等条件与之抗辩的地步。”所以，即使关押修罗王和邪狼的监狱里的每个暗势力之间的关系十分紧张，但为了维持监狱的正常秩序，如非必要，他们会尽可能地避免直接接触。这类似著名的N皇后问题，即在N×N格的国际象棋上摆放N个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，请问有多少种摆法。图所示即是摆法的一种。
输入格式
一行，一个整数N，3<N≤12
输出格式
一行，一个整数，输出一共有多少种摆法
输入输出样列
输入样例1：
4
输出样例1：
2
说明
N=4的棋盘输出的两种方案即图所示。
🔑思路
n个皇后必然分布在n行上，考虑每行上的皇后，可放范围为[1,n]列。
依次搜索每一行上皇后的放置位置，通过判断冲突进行剪枝。
?💯核心代码
bool check(int x,int xn)
{
for(int i=1;i<xn;i++)
{
if(a[i]==x || abs(xn-i)==abs(x-a[i]))return false;
}
return true;
}
void dfs(int x)
{
if(x>n)
{
ans++;
return;
}
for(int i=1;i<=n;i++)
{
if(check(i,x))
{
a[x]=i;
dfs(x+1);
}
}
return;
}素数环[Prime Ring Problem,UVa524]
题目描述
如下图所示，一个圆环是有n个（n是偶数）圆组成的。把自然数1,2...n分别放到n每个圆上，使得两个相邻的数字之和是素数。
注意：第一个圆上的数字始终是1
输入格式
输入有多组数据。
每组数据，一行，一个偶数n，0＜n≤16
输出格式
输出格式，参考输出样例，两组输出之间有一个空行
每一行，代表一个圆环，是从1开始按照逆时针方向输出圆里面的数字。
输入输出样列
输入样例1：
6 8
输出样例1：
Case 1: 1 4 3 2 5 6 1 6 5 2 3 4 Case 2: 1 2 3 8 5 6 7 4 1 2 5 8 3 4 7 6 1 4 7 6 5 8 3 2 1 6 7 4 3 8 5 2
🔑思路
解空间中的每个解包含n-1个元素，每个元素的取值范围为：[2,n]
搜索过程中通过判断i是否已被使用和i+a[cur-1]是否为质数进行剪枝。
