回溯算法-一次搞懂
回溯算法本质上是一种深度优先搜索（DFS），通过递归来模拟“探索所有可能性”的过程。它的核心思想可以总结为三个步骤： 选择 (Choose): 在当前状态下，从所有可能的选择中，选择一个。 探索 (Explore): 基于这个选择，进入下一层决策，即调用递归函数。 撤销选择 (Unchoose): 当下一层的探索全部结束后（无论是找到了解还是走到了死路），退回到当前状态，撤销刚才的选择，然后尝试下一个可用的选择。 几乎所有的回溯问题，都可以用下面这个伪代码模板来解决： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 result = [] // 存放最终结果 path = [] // 存放当前路径 func backtrack(参数列表) { // 1. 终止条件：判断是否找到了一个可行的解 if (满足结束条件) { // 将当前路径的一个副本加入结果集 result.add(path.clone()) return } // 2. 遍历所有可能的选择 for choice in (当前状态下的所有选择) { // 剪枝：如果这个选择不合法，则跳过 if (isPruned(choice)) { continue } // 3....