一、概念

回溯算法也叫试探法，它是一种系统地搜索问题的解的方法。回溯算法的基本思想是：从一条路往前走，能进则进，不能进则退回来，换一条路再试。即满足结束条件或者发现不是正确路径的时候(走不通)，要撤销选择，回退到上一个状态，继续尝试，直到找出所有解为止。

二、代码模板

void dfs(int x) //当前环节
{      
    if(到目的地){

		输出解

		return;

	}

	for(int i = 1; i <=方案数；i++) {   //要试验的情况
		if(方案可行) {

		保存路径

		dfs(x + 1);            //执行下一环节

		恢复保存前状态

        }
    }
}

三、实例分析

给定一个没有重复数字的序列，返回其所有可能的全排列。

输入: [1,2,3]

输出:

[ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ]

（最下面的叶子，红色的就是要求的结果）

然后我们来回想一下，整个问题的思考过程，这棵树是如何画出来的。首先，我们固定1，然后只有2、3可选；如果选2，那就只剩3可选，得出结果 [1,2,3]；如果选3，那就只剩2可选，得出结 果[1,3,2]。再来，如果固定2，那么只有1,3可选：如果选1，那就只剩3，得出结果[2,1,3]...以此类推。

有没有发现一个规律：如果我们固定了（选择了）某个数，那么他的下一层的选择列表就是——除去这个数以外的其他数！！比如，第一次选择了2，那么他的下一层的选择列表只有1和3；如果选择了3，那么他的下一层的选择列表只有1和2,那么这个时候就要引入一个used数组来记录使用过的数字。

#include<bits/stdc++.h>
using namespace std;
int n,a[10005],b[10005];
void work(int nn)
{
    int hh=0;
    if(nn==n+1)  //如果三个位置都已经选完，即选到第四个位置的时候，就可以输出方案
    {
		for(int j=1;j<=n;j++)
			cout<<b[j]<<" ";

		cout<<endl;
    }
    else
    {
        for(int i=1;i<=n;i++) //每个位置有三个数可以选
        {
            if(a[i]==0)   //如果数字没有选过
            {
				b[nn]=i;  //保存数字
				a[i]=1;   //做好标记
				work(nn+1);  //执行下一层
				a[i]=0;   //下一层已经全部执行完毕后，需要还原状态
            }
        }
    }
}

int main()
{
    cin>>n;

    work(1);

    return 0;
}