输出1~n的全排列，其中n由键盘输入。

1>解向量的分析 要求所有排列结果，那么任何一个排列方案，就是问题的一个解，如何表示这个解呢？很显然，我们可以用一个数组int X[MAX]; 这就是解向量。

2>解空间树与回溯函数 每一个解元素的范围都在[1,n]范围，其解空间树如图左侧：

                                图1   回溯函数

回溯函数如图右侧，该函数围绕着X[1]~X[n]的求解，从解空间树的根开始深度优先遍历，其中f(k+1)是对一棵子树进行遍历，每到达一个叶子节点【即if(k-1==n)成立时】，则输出从根到该叶子路径上存储的X[1]~X[n]【每一个非叶子节点处所选择的分支，相当于迷宫的一个岔路口的选择，用对应X[]记录了该岔路口的选择】。从代码中可以看出，并没有创建这棵树，该树是有神而无形。
运行结果图2。

图2 图3 剪枝函数
3>剪枝函数
上面程序，对X[k]取值i时没有任何限制，所以输出结果中数字允许重复出现，而全排列问题，应该让X[k]与X[1]~X[k-1]不重复，也就是X[k]不能取用1~n中的所有值，那么这就是剪枝逻辑，其对应解空间树的遍历逻辑如图3。
4>状态量的设计
前面剪枝函数中，在判断X[k]能否取i时，用了一个循环，依次检查X[1]~X[k-1]中是否已经出现i。显然可以加入一个状态数组int used[ ]，记住i是否已经被使用，这样程序可以改进为：
int X[100],used[100],n; //键盘输入的n小于100
int xianjie(int k, int i)//判断X[k]能否取i
{
if(used[i]) return 0; //used[i]=1时表示数字i已经被使用过
return 1;
}
void f(int k)
{ int i;
if(k-1==n) 输出X[1]~X[n];
else for(i=1;i<=n;i++)
if(xianjie(k,i))
{
X[k]=i;
used[i]=1; //数字i已经被使用的标志，让i在递归f(k+1)里面不会再被使用
f(k+1);
used[i]=0;//f(k+1)结束后，准备遍历另外一棵子树，即下一轮for循环中会尝//试X[k]取i+1的情况，所以数字i的使用状态改回去
}
}
void main(void)
{
cout<<”Enter n:”;
cin>>n;
f(1);
}

归纳：
（1）这是一个“麻雀虽小却五脏俱全”的例子。学会解向量的分析、围绕解向量求解的回溯函数框架、进一步控制解元素取值范围的剪枝函数（即问题提出的各种约束条件）。
（2）弄懂基本原理后，以后基本上可以一步到位的写含有状态量的回溯算法代码，而且只要发现剪枝函数中有循环，基本上都可以考虑设计状态量，从而减轻剪枝函数的运算量。
（3）回溯函数、剪枝函数、输出函数、外加其它辅助函数，区分开来写，而不要全部的逻辑都裹在一起，这样有利于保持自己思路的清晰，出错时好对症下药。
（4）剪枝函数的注意事项，只有最后一个语句是 return 1; 前面全部是return 0的逻辑语句。其形式基本上如下
if(不满足约束的条件1) return 0;
if(不满足约束的条件2) return 0;
…
if(不满足约束的条件n) return 0;
return 1; //不要画蛇添足的去加 “else”

#include<iostream>
using namespace std;
const int N = 10;
int n;
int x[N];
int used[N];
void func(int k);
bool jianzhi(int k, int i);
int main()
{
    cin >> n;
    func(1);
    system("pause");
    return 0;
}

void func(int k)
{
    if (k == n + 1)
    {
        for (int i = 1; i <= n; i++)
            cout << x[i]<<" ";
        cout << endl;
    }
    else
    {
        for (int i = 1; i <= n; i++)
        {
            if (jianzhi(k, i))
            {
                x[k] = i;
                used[i] = 1;
                func(k + 1);
                used[i] = 0;
            }
        }
    }
}
bool jianzhi(int k, int i)
{
    if (used[i] == 1)
        return false;
    return true;
}