DSA - 回溯算法
回溯算法是一种解决问题的方法，它会尝试所有可能的解决方案，并选择最佳或理想的解决方案。通常，它用于解决具有多个解决方案的问题。回溯算法是指，对于给定的问题，如果当前解不合适，则将其排除，然后回溯尝试其他解。
何时使用回溯算法？
回溯算法可用于以下问题 −
问题有多个解或需要找到所有可能的解。
当给定问题可以分解为与原始问题类似的较小子问题时。
如果问题有一些解必须满足的约束或规则
回溯算法如何工作？
回溯算法会探索各种路径，以找到一条通往解决方案的序列路径。沿着这些路径，它会建立一些小的检查点，如果找不到可行解，问题就可以从这些检查点回溯。这个过程会持续下去，直到找到最佳解。
上图中，绿色表示起点，蓝色表示中间点，红色表示没有可行解的点，灰色表示最终解。
当回溯算法到达解的终点时，它会检查这条路径是否为解。如果是解路径，则返回，否则，回溯到上一步以找到解。
算法
以下是回溯算法 −
1. 开始 2. 如果 current_position 是目标点，则返回成功。 3. 否则 4. 如果 current_position 是终点，则返回失败。 5. 否则，如果 current_position 不是终点，则继续探索并重复以上步骤。 6. 停止
回溯的复杂度
通常，回溯算法的时间复杂度是指数级的 (0(kn))。在某些情况下，我们观察到它的时间复杂度是阶乘级的 (0(N!))。
回溯问题的类型
回溯算法适用于一些特定类型的问题。它们如下 −
决策问题 −它用于找到问题的可行解。
优化问题 − 它用于找到可应用的最佳解决方案。
枚举问题 −它用于找到问题所有可行解的集合。
回溯算法示例
以下列表展示了回溯算法 − 的示例。
