回溯简介 - 数据结构和算法教程

回溯(Backtracking)是一种用于解决计算问题的通用算法技术，特别是在算法和数据结构领域。它通常应用于涉及做出一系列选择或决策以达成解决方案的问题。

回溯就像尝试不同的路径，当你遇到死胡同时，你会回溯到最后的选择并尝试不同的路线。

回溯是一种解决问题的算法技术，涉及通过尝试不同的选项来逐步找到解决方案，如果它们导致死胡同则撤消它们。它通常用于需要探索多种可能性来解决问题的情况，例如在迷宫中搜索路径或解决数独等谜题。当到达死胡同时，算法回溯到之前的决策点并探索不同的路径，直到找到解决方案或用尽所有可能性。

回溯背后的基本思想是逐步、系统地探索问题的所有可能解决方案。在每一步中，算法都会做出决定并继续前进。如果在某个时刻，它确定当前路径无法得出有效的解决方案，则会回溯到之前的决策点并探索不同的路径。这个过程一直持续到找到解决方案或用尽所有可能性为止。

回溯算法的关键组成部分是：

1. 决策空间：算法每一步可以做出的所有可能决策或选择的集合。
2. 约束函数：定义一组特定决策有效必须满足的条件或约束的函数。
3. 目标函数：评估一组特定决策是否能产生解决方案的函数。
4. 回溯：当算法确定当前路径无法得出解时，撤销上一个决策并返回到前一个决策点以探索其他可能性的过程。

Python代码：

def find_combinations(nums, target):
    def backtrack(start, target, path):
        if target == 0:
            result.append(path)
            return
        for i in range(start, len(nums)):
            if nums[i] > target:
                continue
            backtrack(i, target - nums[i], path + [nums[i]])

    result = []
    nums.sort()  为优化输入排序
    backtrack(0, target, [])
    return result

Example usage:
nums = [2, 3, 6, 7]
target = 7
print(find_combinations(nums, target))

在此示例中，该backtrack函数探索数组中元素的所有可能组合nums以达到目标总和。如果找到有效的组合，则会将其添加到result列表中。该算法在必要时回溯，探索不同的组合，直到用尽所有可能性。

确定回溯问题：
一般来说，每个约束满足问题都可以使用回溯来解决，但是，每次都使用回溯是最优的吗？事实证明不是，有大量问题可以使用贪心或动态规划以对数或多项式时间复杂度来解决，这远远优于回溯的指数复杂度。然而，仍然存在许多问题只能通过回溯来解决。

为了理解一个问题是否基于回溯，让我们举一个简单的问题：
问题：想象你有 3 个封闭的盒子，其中 2 个是空的，1 个有一枚金币。你的任务是获得金币。

• 为什么动态编程无法解决这个问题？打开或关闭一个盒子对另一个盒子有影响吗？答案是否定的，每一个盒子都是相互独立的，一个盒子的打开/关闭状态并不能决定其他盒子的转换。因此 DP 失败
• 为什么贪心算法不能解决这个问题？贪婪算法选择局部最大值以获得全局最大值，但在这个问题中，每个盒子里有金币的概率都是相同的，即 1/3，因此没有标准来做出贪婪选择。

为什么回溯有效？正如前面所讨论的，回溯算法只是对每个选择进行蛮力计算，因此我们可以逐个选择每个盒子来寻找金币，如果发现某个盒子是空的，我们可以将其关闭，这就是回溯步骤。

从技术上讲，是为了解决回溯问题：

算法通过探索问题中的选择所产生的所有可能路径来建立一个解决方案，这个解决方案从一个空集 S={} 开始。
每个选择都会创建一个新的子树 "s"，我们将其添加到集合中。
现在有两种情况

• S+s 是有效集合
• S+s 不是有效集合

b]回溯伪代码
实现回溯的最佳方法是递归，所有回溯代码都可以按照给出的伪代码进行总结：

void FIND_SOLUTIONS[/b:
if (valid b]solution):
 store the solution
 Return
for (all choice):
 if (valid choice):
   APPLY (choice)
   FIND_SOLUTIONS (parameters)
  BACKTRACK [/b
Return

回溯的复杂性分析
由于回溯算法是纯粹的蛮力算法，因此在时间复杂度方面表现很差。一般来说，回溯具有以下时间复杂性：

• 指数（O(K^N)
• 阶乘（O(N!)