算法描述

回溯算法实际上一个类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就 “回溯” 返回，尝试别的路径。回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为 “回溯点”。许多复杂的，规模较大的问题都可以使用回溯法，有“通用解题方法”的美称。

回溯算法的基本思想是：从一条路往前走，能进则进，不能进则退回来，换一条路再试。

算法使用方法

我觉得在使用回溯算法的时候，需要使用树形的结构来帮助算法的运行。我在使用回溯的时候都是理由深度优先搜索算法和剪枝来解决问题的。

整个深度搜索算法的结构如下：

int n;	// 最终能达到的树的深度
vector<vector<int>> ans; //如果要求不重复，可以声明为set或者在算法中排除
void dfs(int cur, vector<int>tags, vector<int> ins)//cur表示当前到达的树的层次，tag表示一种约束，比如只能元素只能用一次等。ins 表示当前整个路径上的节点。
{
    if(cur == n){//可能还有其他限制条件，这里只是深度满足要求。
        ans.push_back(ins);
        return;
    }
    for(){//遍历可以遍历的
        // 处理tags和ins
        dfs(cur+1, tags,ins);
        //恢复
    }
    return;
}

下面用树形图来解释一下算法：

二叉树

首先就从空节点a开始，每次添加一个节点，从可选的节点中选择，继续到下一层，同时可以存在剪枝，在每个节点开始时，判断是否达到最终条件或者超过最终条件，这样可以将该节点及其以下的节点删除，不用遍历。在遍历子节点完成后，会回到当前节点的上一个状态，这样就是回溯。