前言
●好久不见，十分想念，因为一些事情，九月份耽搁了博客的更新，后续小泉的算法之路和安卓之路即将继续启程。今天小泉想跟大家介绍的是回溯算法。
定义
●以下是回溯法在维基百科上的定义。
回溯法（英语：backtracking）是暴力搜索法中的一种。
对于某些计算问题而言，回溯法是一种可以找出所有（或一部分）解的一般性算法，尤其适用于约束补偿问题（在解决约束满足问题时，我们逐步构造更多的候选解，并且在确定某一部分候选解不可能补全成正确解之后放弃继续搜索这个部分候选解本身及其可以拓展出的子候选解，转而测试其他的部分候选解）。
维基百科从上面的定义可以知晓，回溯法其实遍历了所有解决问题的可能性。
并且根据回溯法的定义，回溯算法，其解决问题是按步进行“试错”，朝着一个方向层层深入，如若某一步发现出错（即已经无法解决问题或者不满足解决问题的条件）之后，就会返回到上一步，重新决定下一步该如何走，反之则继续向下一步进行。最终会得到两种结果：
1.搜索到所有满足问题条件的解决方案
2.不存在满足条件的问题解决方案
那么根据回溯算法的定义以及以前学习DFS的经验，我们可以提出回溯算法的三大要素：
1.路径（Paths）
2.选择（Choose）
3.条件（Condition）
三大要素
1.路径(Paths)
在解决问题之前，需要知晓在当前阶段“下一步”的可选路径有哪些？列出可走路径。
2.选择(Choose)
在知道可选路径之后，就需要进行路径选择。再回退到当前步之前，仅只能选择一条路径前行。
3.条件(Condition)
在选择“下一步”时，需要观察走到现在这一步，目前所在路径是否还满足解决问题的条件，或者是否到达了最后一步，没有“下一步”可走。
算法模板
●算法模板如下
backtracking(step,nowPath,paths){//step:当前步nowPath:当前路径，path:当前步的后续可走的步nowPath.add(step);if(满足解决条件){result.add(nowPath);//加入到解决办法列表里}else{fornextStepinpath{//“选择下一步”nextPath=nextStep.path;result=backtracking(nextStep,nextPath);//进入到下一步}}nowPath.remove(step);//到此说明没有下一步可走，要返回到上一步的状态,那么此步不再保留returnresult;}
根据上面的算法模板，以及处理问题的流程可以看出，回溯算法的实质还是深度优先搜索算法（DFS），其核心思想是递归、止归条件和止归时路径的回退操作。
下面就举两个例子来进行示范。
二叉树中和为某一值的路径
●二叉树中和为某一值的路径
剑指Offer34.二叉树中和为某一值的路径输入一棵二叉树和一个整数，打印出二叉树中节点值的和为输入整数的所有路径。从树的根节点开始往下一直到叶节点所经过的节点形成一条路径。