回溯算法是对树形或者图形结构执行一次深度优先遍历，实际上类似枚举的搜索尝试过程，在遍历的过程中寻找问题的解。

深度优先遍历有个特点：当发现已不满足求解条件时，就返回，尝试别的路径。此时对象类型变量就需要重置成为和之前一样，称为「状态重置」。

许多复杂的，规模较大的问题都可以使用回溯法，有「通用解题方法」的美称。实际上，回溯算法就是暴力搜索算法，它是早期的人工智能里使用的算法，借助计算机强大的计算能力帮助我们找到问题的解。

深度优先搜索算法的代码框架：

ans;
void dfs(层数,其他参数)
{
    //递归边界
    if(边界判断)
    {
        更新答案；
        return;
    }
    //尝试所有的可能性
    for(枚举下一层可能的情况)
    {
        if(vis[i]==0)//如果状态i没有用过，就可以进入下一层
        {
            vis[i]=1;//标记状态i，表示已经用过，在下一层及之后不再使用
            dfs(层数+1,其他参数);
            vis[i]=0;//恢复状态i，回溯时不影响下一层及之后的使用
        }
    }
    return;
}