全排列问题与八皇后问题是理解递归与分治思想的重要例子

一、什么是递归与分治？

在系统地学习数据结构的过程中，在研读了许多博主关于全排列及八皇后问题求解的具体算法后，在对递归与分治原理的理解上有了长足的进步。在解决问题时运用分治法的本质就是在解决问题时将之分解为若干个性质上与原问题一致或相似的小规模子问题是可以通过进一步分解为更小规模的问题来处理从而可以用相同的求解策略去逐一攻克每个小规模的问题由此可见 在设计求解策略时采用递归的思想往往能够有效地实现这一目标

例如：采用递归策略实现二叉树的先根、中根及后根遍历方法；通过分治策略求解最大子序列和问题；利用递归来解决经典的斐波那契数列计算问题；此外如汉诺塔问题等都体现了这一核心思想

二、全排列问题

我们可以将从1到n的这些整数按照某种顺序进行排列的结果称之为它们的一个排列组合；而所有的这些不同排列组合则构成了一个完整的集合体。

基于递归与分治策略分析问题时

值得注意的是递归的递归边界！

 #include<cstdio>

    
 #include<iostream>
    
 using namespace std;
    
  
    
 const int maxn=11;
    
 /*p为当前排列，hashTable[maxn]记录整数是否已经在p中*/
    
 int n,p[maxn],hashTable[maxn]={false};