回溯算法是一种递归模式，它是一种暴力求解方法(brute force method)，用于求出所有可能的解，回溯算法通常会构建一个状态空间树(state space tree),

将可能的组和从根到叶节点进行展开，然后以深度优先的方式搜索遍历状态树，遍历过程中遇到不符合解的节点立马返回进行新的遍历，而不是继续遍历，

状态空间树的结构可用下图进行描述：

 回溯算法不是用来求解最优解，而是用来求解可行解的方法，回溯算法的代码结构：

Backtrack(x)
    if x is not a solution
        return false  // return directly
    if x is a new solution
        add to list of solutions
    backtrack(expand x)

根据以上结构，用具体的示例进行分析，例如：

1、排队问题，假设有2个男孩和1个女孩，女孩不能站在男孩的中间，则可以用一个树的结构进行描述：

 树是构建好了，根据构建树构建代码：

arrange-boy-girl(p,index,result,mem)://index 用于记录孩子的位置，result是最终的排列结果，mem用于记录孩子是否已经排在队中了

　　if index == p.length:

　　　　print(result);//输出结果

　　// expand p

　　for i =0 to p.length:

　　　　if(index == 2 && p[i]=='girl' || mem[i] ==1)://位置2不能是女孩,且该小孩没有在队列中，继续进行循环

　　　　　　continue;　　　　

　　　　result[index]=p[i];//将小孩排到队中

　　　　mem[i]=1;//记录一下，下次这个小孩不能再排了，因为已经在队伍中了

　　　　index++;//排下一个位置

　　　　arrange-boy-girl(p,index,result,mem);//递归调用，排下一个位置

　　　　index--;//注意这里，index恢复原值，表示原来的index位置还可以安排下一个小孩，比如，位置0可以是boy1,也可以是boy2

　　　　mem[i]=0;//这里也是，index恢复原值后，mem也要恢复原值

以上是一个全排列问题，但是它有一些限制，就是女孩不能排到男孩儿中间。

2、数的组合排列问题，给定一个数组 1 2 3，可以拼成多少种不同的两位数，每个数都可以重复利用，先构建组合树：

以上构建的是两位数，根据同样的方式还可以继续构建，可以是3位数，4位数，根据构建树编写程序：

combine-num(arr,depth,result):

　　//递归的结束条件

　　if depth == 2:

　　　　print(result);

　　// expand array　　

　　for int i =0 to arr.length:　　　　

　　　　result.add(arr[i]);//添加元素

　　　　depth++;//走到下一个位置

　　　　combine-num(arr,depth,result);

　　　　depth--;//回溯到上一个位置

　　　　result.removeLastNum();//将当前位置元素删除，相当于回溯到上一个位置以存放for循环中的第i+1个元素

本示例中，递归的结束条件是depth=2，如果需要是3位数，则depth=3，注意这里的“回溯”是在哪里体现的，就是“depth--”那个位置，表示返回

到上一个位置，将该位置放置第（i+1）个元素。

3、子集和的问题，给定一个集合{1，2，3，4，5，6，7，8，9，10}和一个值val=15，判断该集合中是否存在元素和为val的子集，如果有则输出该子集；

这个和上面的是一样的，也是一个组合问题，但是为了避免重复解的出现，比如 7+8=15，8+7=15；可以让每个元素只和它后面的元素进行组合；构造程序

如下：

def subset-sum(arr,fromIndex,sum,val,result):

　　if sum==val:

　　　　print(result);

　　for i=fromIndex to arr.length:

　　　　sum+=arr[i];//加上当前元素

　　　　result.add(arr[i]);//将当前元素放到子集中

　　　　subset-sum(arr,i+1,sum,val,result);// 注意这里，fromIndex变为了i+1,也就是当前元素只能和它后面的元素进行组合

　　　　sum-=arr[i];//减去当前元素，回溯到上一个子集和的状态

　　　　result.removeLast();//删除当前元素，回溯到上一个子集状态

4、八皇后问题，在8*8的空格列表中，每个空格可以放一个皇后，皇后可以攻击与它同行或同列的其他皇后，在该列表中摆放8个皇后，使其不能

互相攻击，求一共有多少种摆放方法；首先构造树结构，这里有一个4*4的列表结构：

从这棵树的构造过程，可以大体得出代码的构造过程，根节点到叶子节点的距离就是该叶子节点的深度，其实也就是行数rows；每行中空格的个数也就是

表格的列数cols，可以创建一个arr[rows][cols]的二维数组，然后构建代码：

N-Queens(arr,rows,cols,row):

　　if row == rows://当前树的深度为表格的行数，也就是所有行都遍历了，则打印出结果

　　　　print(arr);

　　else:

　　　　for col=0 to cols://遍历第depth行中的每个空格

　　　　　　if isValid(arr,row,col,rows,cols):

　　　　　　　　arr[row][col]=1;

　　　　　　　　row+=1;//移动到下一行

　　　　　　　　N-Queen(arr,rows,cols,row);//遍历下一行

　　　　　　　　row-=1;//回溯到上一行，对上一行的下一个元素继续递归运算

　　　　　　　　arr[row][col]=0;//将原来位置重新恢复原值0，注意这里代码是有先后顺序的，row-=1在前，恢复原值在后

　　　　　　else:

　　　　　　　　continue;//继续遍历该行的下一个元素

这里有一个isValid方法，用于判断row行和col列中没有皇后存在：

isValid(arr,row,col,rows,cols):

　　for i=0 to rows and i!=row

　　　　if arr[i][col]==1     　　return false; //存在皇后，该列非法

　　for i=0 to cols and i!=col

　　　　if arr[row][i]==1 　　　return false; //存在皇后，该行非法　　　　　

　　return true;//该空格所在的行和列都不存在皇后，是合法位置

总结：

回溯算法是和递归相关的，首先需要构建一个状态空间树，在代码层面是通过遍历和递归的形式构建一颗逻辑性的状态空间树，而非真的创建一个

树型的数据结构，在遍历和递归的过程中，这些执行路线构成了一个状态空间树，回溯算法的代码接口可如下表示：

backtrace(arr,result,xx):

　　if xx满足条件：

　　　　print(result)

　　else

　　　　for el in arr: //expand arr

　　　　　　result.add(el);//做选择

　　　　　　update xx;//更新条件

　　　　　　backtrace(arr,result,xx);

　　　　　　cancel xx;//撤销条件

　　　　　　result.delete(el);//撤销选择　　

回溯的难点就是构造树的过程，这是一个逻辑形式上的构建，通过遍历和递归加以实现，同时需要对执行过程对状态更新和撤销。