第七章 回溯算法理论基础

一、定义

回溯法也可以叫做回溯搜索法，是一种搜索方式。

回溯和递归是孪生兄弟，同出同没。 回溯=递归

1.1回溯的效率

回溯的效率并不高，本质是一个枚举，之所以学它，是因为某些场合下必须用回溯法解决问题。

回溯可以解决如下的问题：

• 组合问题【N个数里面按一定规则找出k个数的集合】
• 切割问题【一个字符串按一定规则有几种切割方式】
• 子集问题【一个N个数的集合里有多少符合条件的子集】
• 排列问题【N个数按一定规则全排列，有几种排列方式】组合无序，排列有序。
• 棋盘问题【N皇后，解数独等等】

1.2回溯法的理解

回溯法可以理解成一种树形结构。这个结构具有 深度、高度。

二、回溯法的模板

回溯法是可以理解成树形结构，所以他的模板和递归模板一样也是三部曲！

回溯法三部曲：

void backtracking(参数)

if(终止条件){
    存放结果;
    return;
}

for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {//回溯逻辑处理
    处理节点;
    backtracking(路径，选择列表); // 递归
    回溯，撤销处理结果
}

• 整理一下模板、完整如下：

void backtracking(参数) {
    if (终止条件) {
        存放结果;
        return;
    }
    for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
        处理节点;
        backtracking(路径，选择列表); // 递归
        回溯，撤销处理结果
    }
}