什么是回溯算法

回溯算法（backtracking algorithm）是一种通过穷举来解决问题的方法，它的核心思想是从一个初始状态出发，暴力搜索所有可能的解决方案，当遇到正确的解则将其记录，直到找到解或者尝试了所有可能的选择都无法找到解为止。之所以称之为回溯算法，是因为该算法在搜索解空间时会采用“尝试”与“回退”的策略。当算法在搜索过程中遇到某个状态无法继续前进或无法得到满足条件的解时，它会撤销上一步的选择，退回到之前的状态，并尝试其他可能的选择。比如说我们在二叉树上查找有否有值等于10：

/* 前序遍历：例题二 */voidpreOrder(TreeNoderoot){Listpath=newLinkedArrayList<>();// 剪枝,也称约束条件if(root==null){return;}// 尝试path.add(root);if(root.val==10){// 记录解res.add(newArrayList<>(path));}preOrder(root.left);preOrder(root.right);// 回退path.remove(path.size()-1);}

回溯算法本质上是一种深度优先搜索算法，它尝试所有可能的解决方案直到找到满足条件的解。这种方法的优点在于能够找到所有可能的解决方案，而且在合理的剪枝操作下，具有很高的效率。然而，在处理大规模或者复杂问题时，回溯算法的运行效率可能难以接受。
1，时间：回溯算法通常需要遍历状态空间的所有可能，时间复杂度可以达到指数阶或阶乘阶。
2，空间：在递归调用中需要保存当前的状态（例如路径、用于剪枝的辅助变量等），当深度很大时，空间需求可能会变得很大。
即便如此，回溯算法仍然是某些搜索问题和约束满足问题的最佳解决方案。对于这些问题，由于无法预测哪些选择可生成有效的解，因此我们必须对所有可能的选择进行遍历。在这种情况下，关键是如何优化效率，常见的效率优化方法有两种。
1，剪枝：避免搜索那些肯定不会产生解的路径，从而节省时间和空间。
2，启发式搜索：在搜索过程中引入一些策略或者估计值，从而优先搜索最有可能产生有效解的路径。
回溯算法也有许多经典的应用，可用于解决许多搜索问题、约束满足问题。