总结
要点总结
- 回溯算法的本质是暴力穷尽，一般使用深度优先搜索来寻找符合条件的解。搜索过成功中，遇到满足条件的则记录，直到遍历完所有情况，或者满足条件。
- 回溯算法分为尝试和回退。它通过深度优先搜索来尝试各种选择，当遇到不满足约束条件的情况时，则撤销上一步的选择，退回到之前的状态，并继续尝试其他选择。尝试与回退是两个方向相反的操作。
- 回溯过程常常包含约束条件，可以用于进行剪枝。减少不必要的遍历情况。
- 回溯算法主要可用于解决搜索问题和约束满足问题。组合优化问题虽然可以用回溯算法解决，但往往存在效率更高或效果更好的解法。
Q & A
如何理解回溯和递归的关系。
总的来看，回溯是一种“算法策略”，而递归更像是一个“工具”。
回溯算法通常基于递归实现。然而，回溯是递归的应用场景之一，是递归在搜索问题中的应用。 递归的结构体现了“子问题分解”的解题范式，常用于解决分治、回溯、动态规划（记忆化递归）等问题。