掌握Python回溯算法（从零开始学会回溯法解决经典问题）

回溯算法的基本框架

一个典型的回溯算法包含以下几个要素：

• 路径（path）：已经做出的选择。
• 选择列表（choices）：当前可以做的选择。
• 结束条件（base case）：到达决策树的底层，无法再做选择。

其通用代码结构如下：

def backtrack(路径, 选择列表):    if 满足结束条件:        result.append(路径[:])  # 注意要拷贝路径        return        for 选择 in 选择列表:        做选择（将选择加入路径）        backtrack(路径, 新的选择列表)        撤销选择（从路径中移除）

实战案例：全排列问题

我们以经典的“全排列”问题为例：给定一个不含重复数字的数组，返回其所有可能的排列。

例如，输入 [1,2,3]，输出应为：

[[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]

下面是使用回溯法教程中介绍的方法实现的Python代码：

def permute(nums):    result = []    path = []    used = [False] * len(nums)  # 标记元素是否已被使用        def backtrack():        # 结束条件：路径长度等于原数组长度        if len(path) == len(nums):            result.append(path[:])  # 拷贝当前路径            return                for i in range(len(nums)):            if used[i]:                continue  # 跳过已使用的元素                        # 做选择            path.append(nums[i])            used[i] = True                        # 递归进入下一层            backtrack()                        # 撤销选择（回溯）            path.pop()            used[i] = False        backtrack()    return result# 测试print(permute([1, 2, 3]))

为什么需要“撤销选择”？

这是理解递归与回溯的关键！因为 path 是一个可变对象（列表），在递归过程中会被多个函数调用共享。如果不撤销选择，那么上一次递归留下的“痕迹”会影响下一次尝试，导致结果错误。

通过 path.pop() 撤销最后一步操作，我们确保每次回溯后，状态恢复到进入该递归层之前的样子，从而保证下一次循环的“干净”起点。

常见应用场景

除了全排列，回溯算法还适用于以下问题：

• 组合问题（如从1-9中选k个数使其和为n）
• 子集生成
• N皇后问题
• 解数独
• 单词搜索（Word Search）

小结

通过本篇算法设计入门教程，你应该已经掌握了回溯算法的核心思想：**选择 → 递归 → 撤销**。记住，回溯的本质是“暴力搜索 + 剪枝优化”，虽然时间复杂度可能较高，但对于许多组合类问题，它是最直观且有效的解法。

建议你动手实现几个经典问题（如子集、组合、N皇后），加深对回溯过程的理解。随着练习增多，你会逐渐掌握如何设计“选择”、“路径”和“结束条件”。

关键词回顾：Python回溯算法、回溯法教程、算法设计入门、递归与回溯。