回溯算法模板

在讲二叉树的递归中我们说了递归三部曲,这里我再给大家列出回溯三部曲。

1 回溯函数模板返回值以及参数

在回溯算法中,我的习惯是函数起名字为backtracking,这个起名大家随意。

回溯算法中函数返回值一般为void

再来看一下参数,因为回溯算法需要的参数可不像二叉树递归的时候那么容易一次性确定下来,所以一般是先写逻辑,然后需要什么参数,就填什么参数

回溯函数伪代码如下:

void backtracking(参数)

2 回溯函数终止条件

既然是树形结构,那么我们在讲解二叉树的递归的时候,就知道遍历树形结构一定要有终止条件。

所以回溯也有要终止条件。

什么时候达到了终止条件,树中就可以看出,一般来说搜到叶子节点了,也就找到了满足条件的一条答案,把这个答案存放起来,并结束本层递归。