backtrack算法

概念和基本思想

走不通就退回再走的技术成为回溯法，满足回溯条件的某个状态点成为回溯点。
在包含问题的所有解的解空间树中，按照深度优先的策略，从根节点出发深度优先搜索，搜索到某个点的时候，先判断该节点是否包含问题的解，如果包含就继续探索，否则就逐层向根节点回溯。

步骤

确定问题的解空间
确定节点的扩展搜索规则
深度优先的方式搜索解空间，并在搜索过程中剪枝函数避免无效搜索

void dfs()//参数用来表示状态
{
    if(到达终点状态)
    {
        ...//根据题意来添加
        return;
    }
    if(越界或者是不符合法状态)
        return;
    for(扩展方式)
    {
        if(扩展方式所达到状态合法)
        {
            ....//根据题意来添加
            标记；
            dfs（）；
            修改（剪枝）；
            还原标记； 
        }
        
    }
}