Skip to main content

​
核心认知

回溯算法本质上是一种搜索。 它的典型过程是：
  1. 做一个选择
  2. 进入下一层递归
  3. 撤销这个选择
  4. 尝试别的分支
所以回溯的核心不是“递归”本身，而是“搜索 + 撤销选择”。

​
哪类问题适合回溯

如果题目要求：
  • 求所有结果
  • 求所有合法组合
  • 求所有排列
  • 列举全部路径
那回溯通常就是非常自然的方向。 这类题最典型的特征是：每一步都有多个选择，而且你需要把整棵搜索树走完。

​
回溯模板里最重要的三个元素

写回溯时，你最好先明确这三件事：
  • 当前路径是什么
  • 当前还能选什么
  • 什么时候收集答案
如果这三个点没想清楚，代码通常会变得很乱。

​
为什么一定要撤销选择

因为你不是只走一条路径，而是要回到岔路口，继续探索别的分支。 
def subsets(nums: list[int]) -> list[list[int]]:
    result: list[list[int]] = []
    path: list[int] = []

    def backtrack(start: int) -> None:
        result.append(path[:])

        for i in range(start, len(nums)):
            path.append(nums[i])      # 做选择
            backtrack(i + 1)          # 向下搜索
            path.pop()                # 撤销选择

    backtrack(0)
    return result
这段代码里最关键的一句不是递归，而是 path.pop()。
没有撤销，搜索树就走不干净。

​
回溯为什么总画成一棵树

因为它真的就是在树上搜索。 每往下一层，表示你多做了一个选择。
每回退一步，表示你放弃当前分支，重新试别的可能。 所以做回溯题时，一个非常有效的方法是先在草稿纸上把搜索树大致画出来。

​
常见题型

回溯题常见有这些模型：
  • 组合
  • 排列
  • 子集
  • 字符串切割
  • 棋盘问题
  • 去重搜索
虽然题型名字不同，但很多代码骨架是相似的。

​
剪枝为什么比模板更重要

回溯本质上是暴力搜索。
真正让它变快的，往往不是模板，而是剪枝。 常见剪枝包括：
  • 当前路径已经不合法，立即返回
  • 当前和已经超过目标值，停止向下搜
  • 同层去重，避免重复结果
如果你能找到有效剪枝点，性能会差很多。

​
学习建议

建议按这个顺序练：
  • 组合
  • 子集
  • 排列
  • 组合总和
  • 分割回文串
  • N 皇后
当你开始习惯把回溯题看成“在树上遍历所有可能性”，很多题会自然归类。