【算法】回溯法

回溯法（Backtracking）是一种通过系统地搜索问题的解空间来找到所有可能结果或最佳解的算法设计范式。它广泛应用于解决各种组合优化问题，比如图的着色、数独求解、八皇后问题、旅行商问题等。

在程序中，回溯法通常表现为递归函数。

递归代码的基本结构是一种自我调用的方式，用来解决可以被分解为子问题且具有重复结构的问题。

一、 递归代码的基本通用模板

def recursive_function(parameters):
    # 1. 基线条件 (Base Case): 定义递归何时停止
    if some_condition:
        return some_value  # 一旦满足条件，直接返回结果，结束递归

    # 2. 递归过程 (Recursive Case): 将问题分解为子问题，再递归调用自身
    # 例如，计算更小规模的问题
    smaller_problem_result = recursive_function(smaller_parameters)

    # 3. 合并子问题的结果并返回
    result = do_some_operations(smaller_problem_result)
    return result

1. 基线条件（Base Case）

• 作用：为递归设立清晰的停止点，避免无限递归。
• 设计方式：要满足递归逻辑的结束条件，例如问题规模缩小到 0、1，或者已经达到了目标条件等。

2. 递归过程（Recursive Case）

• 作用：将问题规模缩小，递归解决规模更小的子问题。
• 设计方式：
  • 提取当前层的问题需要解决的部分。
  • 为剩余的子问题递归调用自身。
  • 每一级调用后，都会处理一些局部问题，然后把剩下的部分交给接下来的递归。

3. 合并结果

• 作用：将子问题递归返回的结果整合，形成当前问题的解。
• 设计方式：合并或加工子问题数据（例如加和、拼接、选取最优解等），最后返回结果。

二、 示例：全排列（Permutations）

1. 代码实现

from typing import List

def permute(nums: List[int]) -> List[List[int]]:
    # 1. 基线条件：当列表为空时，返回一个空排列 [[]]
    if not nums:
        return [[]]

    # 2. 递归过程：让每个数字轮流作为第一个元素
    result = []
    for i, num in enumerate(nums):
        # 剩余子问题
        remains = nums[:i] + nums[i+1:]
        # 对剩余部分递归求全排列
        permutations = permute(remains)

        # 3. 合并结果：将当前数字与子问题的结果拼接
        for perm in permutations:
            result.append([num] + perm)

    return result

为列表 nums = [1, 2, 3]，生成所有排列：

nums = [1,2,3]
result = permute(nums)
print(result)

以上述调用代码为例，我们将用 显式栈 来模拟递归过程，并结合输入 nums = [1, 2, 3] 展示每一步的调用堆栈。递归函数调用实际上会通过系统栈记录调用信息，直到递归的返回条件触发为止。

2. 递归的堆栈过程

初始调用是 permute([1, 2, 3])。整个递归的堆栈过程包括两部分：

1. 递归展开：函数调用不断深入，分解问题。
2. 递归回溯（收缩）：从底层结果开始逐步返回，拼接结果。

2.1 堆栈结构：

permute([1, 2, 3])   
result = []
└── 处理中：num = 1, remains = [2, 3]
    └── permute([2, 3])
        result = []
        └── 处理中：num = 2, remains = [3]
            └── permute([3])
                result = []
                └── 处理中：num = 3, remains = []
                    └── permute([])
                        result = [[]]  # 基线条件，返回空排列
                    拼接：result = [[3]]  # 将 num = 3 加入
                返回：[[3]]
            拼接：result = [[2, 3]]  # 将 num = 2 加到子问题 [[3]]
        └── 处理中：num = 3, remains = [2]
            └── permute([2])
                result = []
                └── 处理中：num = 2, remains = []
                    └── permute([])
                        result = [[]]  # 基线条件，返回空排列
                    拼接：result = [[2]]  # 将 num = 2 加入
                返回：[[2]]
            拼接：result = [[3, 2]]  # 将 num = 3 加到子问题 [[2]]
        返回：[[2, 3], [3, 2]]	# result.append
    拼接：result = [[1, 2, 3], [1, 3, 2]]  # 将 num = 1 加到子问题 [[2, 3], [3, 2]]
└── 处理中：num = 2, remains = [1, 3]
    └── permute([1, 3])
        result = []
        └── 处理中：num = 1, remains = [3]
            └── permute([3])
                result = []
                └── 处理中：num = 3, remains = []
                    └── permute([])
                        result = [[]]  # 基线条件，返回空排列
                    拼接：result = [[3]]  # 将 num = 3 加入
                返回：[[3]]
            拼接：result = [[1, 3]]  # 将 num = 1 加到子问题 [[3]]
        └── 处理中：num = 3, remains = [1]
            └── permute([1])
                result = []
                └── 处理中：num = 1, remains = []
                    └── permute([])
                        result = [[]]  # 基线条件，返回空排列
                    拼接：result = [[1]]  # 将 num = 1 加入
                返回：[[1]]
            拼接：result = [[3, 1]]  # 将 num = 3 加到子问题 [[1]]
        返回：[[1, 3], [3, 1]]
    拼接：result = [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1]]  # 将 num = 2 加到子问题 [[1, 3], [3, 1]]
└── 处理中：num = 3, remains = [1, 2]
    └── permute([1, 2])
        result = []
        └── 处理中：num = 1, remains = [2]
            └── permute([2])
                result = []
                └── 处理中：num = 2, remains = []
                    └── permute([])
                        result = [[]]  # 基线条件，返回空排列
                    拼接：result = [[2]]  # 将 num = 2 加入
                返回：[[2]]
            拼接：result = [[1, 2]]  # 将 num = 1 加到子问题 [[2]]
        └── 处理中：num = 2, remains = [1]
            └── permute([1])
                result = []
                └── 处理中：num = 1, remains = []
                    └── permute([])
                        result = [[]]  # 基线条件，返回空排列
                    拼接：result = [[1]]  # 将 num = 1 加入
                返回：[[1]]
            拼接：result = [[2, 1]]  # 将 num = 2 加到子问题 [[1]]
        返回：[[1, 2], [2, 1]]
    拼接：result = [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]  # 将 num = 3 加到子问题 [[1, 2], [2, 1]]
返回：[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]

注意：递归函数的每次调用都有独立的上下文，每一层的result都是完全不同的变量

2.2 具体过程：

输入：nums = [1, 2, 3]

1. 第一层递归：调用 permute([1, 2, 3])

   • 迭代 nums：
     • 第一个数字为 1，remains = [2, 3]，递归调用 permute([2, 3])。

2. 第二层递归：调用 permute([2, 3])

   • 迭代 nums：
     • 第一个数字为 2，remains = [3]，递归调用 permute([3])。

3. 第三层递归：调用 permute([3])

   • 迭代 nums：
     • 第一个数字为 3，remains = [] ，递归调用 permute([])。

4. 第四层递归：调用permute([])

   • 迭代nums:
     • 由于 nums = []，触发基线条件 if not nums。
       • 返回结果 permutations = [[]]（空排列）

5. 返回第三层：

   • 遍历permutations = [[]]：
     • 将 3 拼接到每个排列：[3] + [] = [3]。
       • 当前结果 result = [[3]]。返回 [[3]]。

6. 返回第二层：

   • 处理 permute([2, 3]) 的第一个分支
     • 遍历 permutations = [[3]]，将 2 拼接到每个排列：[2] + [3] = [2, 3]。
       • 当前结果 result = [[2, 3]]。

7. 继续处理 permute([2, 3]) 的第二个分支:

   • 第二次选取 num = 3，剩余数字 remains = [2]。
     • 递归调用 permute([2])

8. 递归处理 permute([2])：

   • 遍历 nums = [2]，进入循环：
     • 第一次选取 num = 2，剩余数字 remains = []，递归调用 permute([])。

9. 递归处理permute([])：

   • 迭代nums:
     • 由于 nums = []，触发基线条件 if not nums。
       • 返回结果 permutations = [[]]（空排列）

10. 返回上一层：

    • 遍历 permutations = [[]]，将 2 拼接到每个排列：[2] + [] = [2]。
      • 当前结果 result = [[2]]。

11. 返回第二层：

    • 处理 permute([2, 3]) 的第二个分支
      • 遍历 permutations = [[2]]，将 3 拼接到每个排列：[3] + [2] = [3, 2]。
        • 当前结果 result = [[2, 3], [3, 2]]。

12. 返回第一层：

    • 处理 permute([1, 2, 3]) 的第一个分支
      • 遍历 permutations = [[2, 3], [3, 2]]，将 1 拼接到每个排列：[1] + [2, 3] = [1, 2, 3]，[1] + [3, 2] = [1, 3, 2]。
        • 当前结果 result = [[1, 2, 3], [1, 3, 2]]。

13. 回到 permute([1, 2, 3])
    当前栈为：

permute([1, 2, 3])
└── 处理中：num = 2, remains = [1, 3]

重复对剩下的分支处理（递归展开 + 收缩）

后续操作类似：

• 处理 num = 2, remains = [1, 3]，递归展开成 [[1, 3], [3, 1]]，最终拼接得出 [[2, 1, 3], [2, 3, 1]]。
• 再处理 num = 3, remains = [1, 2]，递归展开成 [[1, 2], [2, 1]]，最终拼接得出 [[3, 1, 2], [3, 2, 1]]。

返回最终结果：

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