递归回溯用于解决全排列问题(两种解决思路)

打印全排列问题：给定一个数值n，需要输出由1至n构成的所有可能排列。例如当n=4时，所有排列形式如下所示：

1 2 3 4

1 2 4 3

1 3 2 4

1 3 4 2

1 4 2 3

1 4 3 2

......

4 1 2 3

总计共有4!=24种排列方式。

———————————————————————————————————————————————————

方法一：[选择+递归+回溯]****

我们采取一种易于理解 的实现方式，依次生成所有可能的排列组合.

思路：设定数组a[]，从a[1]位置开始到a[n]位置，从数字集合1~n中选取一个数放置于a[1]的位置，接着继续选取下一个数并置于a[2]的位置……对于已被选用的数字进行标记，并结合递归与回溯机制完成整个过程.

代码如下：

 #include<iostream>

    
 using namespace std;
    
  
    
 int n;
    
 int a[101];//记录排列
    
 int vis[101];//标记数组
    
 int tot;//排列数
    
  
    
 void f(int k)//k为当前位置
    
 {
    
 	if(k==n+1)//K=n+1说明a[n]处的元素已经选完了，此