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

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

链接：https://leetcode-cn.com/tag/backtracking/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

联系： 看到上面的回溯算法的基本思想你可能会想，回溯算法和深度优先搜索有什么区别和联系呢？其实 回溯法通常和深度优先搜索相联系，如果当前的路径走不通时，就后退一步，然后继续走（这和深度优先搜索DFS）相似。其实回溯法通常会借助DFS来求解，回溯搜索就是深度优先搜索（DFS）的一种。对于某一个搜索树来说（搜索树是起记录路径和状态判断的作用），回溯和DFS，其主要的区别是，回溯法在求解过程中不保留完整的树结构，而深度优先搜索则记下完整的搜索树。为了减少存储空间，在深度优先搜索中，用标志的方法记录访问过的状态，这种处理方法使得深度优先搜索法与回溯法没什么区别了。 区别： 深度优先遍历：已经访问过的节点不再访问，所有点仅访问一次。 回溯法：已经访问过的点可能再次访问，也可能存在没有被访问过的点。 （区别不止这一个，只不过这个比较有象征性）

题目链接 输入一棵二叉树和一个整数，打印出二叉树中节点值的和为输入整数的所有路径。从树的根节点开始往下一直到叶节点所经过的节点形成一条路径。

首先要用一个向量来记载走的路径，从根节点向下走，如果到达叶子节点，并且路径和等于目标值时，就把该路径记录到一个二维向量中。如果到达叶子节点但是路径和不等于目标值时，那么就向上回溯。本来递归左右子树就是要向上回溯，这时当一个节点的左右子树都被遍历过，那么就把路径记录值弹出来，让路径的记录值也同时向上回溯，然后遍历完所有节点即可得到该题的解。

题目链接 **题目描述：**给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。 candidates 中的数字可以无限制重复被选取。 说明： 所有数字（包括 target）都是正整数。 解集不能包含重复的组合。 输入输出：

从前(下标为m处)往后遍历向量candidates，只要当前的值小于或等于target-sum，就把该数字存入路径向量temp中，如果当前的值大于target-sum，就继续往后遍历,遍历完整个数组，就回溯，把路径向量弹出最后面的，然后从再从下标为n+1处遍历数组，（如果当前的sum值等于目标target值，就把当前的路径保存起来）直到从每一个下标开始的情况都考虑完，那么问题的解就求出来了。